文章目录
- 数据对拍
- 举例
- dp
- 暴力
- 数据对拍
- 总结
数据对拍
使用数据对拍的功能来检测代码有没有出错误。
步骤：针对某个题的做题过程
- 首先写这道题的你认为的优化做法，因为一般的算法竞赛中肯定不可能是暴力的。
- 然后写这道题的暴力做法。
- 然后写数据对拍器，比较数据的差异
举例
dp
对于背包问题我们可以有 dp动态规划的做法（这是最基本的），代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
int n,v;
int nums[N],val[N],dp[N];
int main()
{
cin>>n>>v;
for (int i=1;i<=n;i++){
cin>>nums[i]>>val[i];
}
for (int i=1;i<=n;i++){
for (int j=v;j>=nums[i];j--){
dp[j]=max(dp[j],dp[j-nums[i]]+val[i]);
}
}
cout<<dp[v];
return 0;
}暴力
对于01背包的暴力方法，我们考虑二进制枚举的思想。
对于每一个 n，我们都把它转换为二进制的形式，其中 1表示选择这个物品，0表示不选择这个物品，则通过暴力枚举二进制的所有的01情况，来得到每一种情况的背包价值，然后得到ans
假设n=5 ，则我们需要枚举 00000 - 11111共32种情况，即 1<<5种，然后通过一层循环来获得二进制中所有的1，然后进行数据的累加。
注意我们的范围都是从 0开始的，因为二进制中全0表示都不选，全1表示全选，因此我们的for循环要写成这样的形式：
for (int i=0;i<(1<<n);i++)代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
int n,W;
int w[N],v[N];
int main(){
cin>>n>>W;
for (int i=0;i<n;i++){
cin>>w[i]>>v[i];
}
int ans=0;
for (int i=0;i<(1<<n);i++){
int sumv=0,sumw=0;
for (int j=0;j<n;j++){
if (i>>j&1){
sumv+=v[j];
sumw+=w[j];
}
}
if (sumw<=W){
ans=max(ans,sumv);
}
}
cout<<ans;
return 0;
}数据对拍
然后就到了我们的重头戏：数据对拍，首先把生面生成的两个exe放到同一文件夹下面
基本思路：
- 通过随机产生数据，把数据存储到
input.txt中。 - 对于上面的两个
exe程序，从文件读取内容，然后分别把两个运行的结存储到两个xx_out,txt文件中。 - 然后比较这两个
xxx_out.txt文件内容是否是一致的。
如何进行文件的读写？
- 头文件：
#include <fstream>表示对文件流操作； -
ofstream out(input.txt)输出重定向到文件中 -
ifstream in(input.txt)输入重定向到文件中
system对文件的操作
-
system("dp.exe < input.txt > dp_out.txt")，dp解法从文件读取数据，然后把dp.exe的输出重定向到dp_out.txt中；对于暴力也是同理。 -
system("fc dp_out.txt baoli_out.txt")，比较两个文件是否存在差异。
如果没有差异，证明我们写的解法基本上是正确的。
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
void generate_data(){
ofstream out("input.txt");
out<<10<<' '<<rand()%200+50<<endl;//物品数量和背包容量
for (int i=1;i<=10;i++){
int w=rand()%50+10,v=rand()%50+10;
out<<w<<' '<<v<<endl;
}
out.close();
}
int main(){
for (int i=1;i<=100;i++){
cout<<"i = "<<i<<":";
generate_data();
system("dp.exe < input.txt > dp_out.txt");
system("baoli.exe < input.txt > baoli_out.txt");
system("fc dp_out.txt baoli_out.txt");
}
return 0;
}总结
通过手写两种解法（优化 and 暴力）并且通过数据对拍的功能来实现降低我们程序出错的可能性，数据对拍在蓝桥杯等竞赛中是一个不错的技巧。