优化代码#include<iostream> #include<algorithm> using namespace std; const int N=2023; int n,m=0; int f[N][N]; int v[N],w[N]; int main () { cout<<"请输入有几件物品,和最大重量:"<<endl; cin>>n>>m; //有几件物品和最大能够承受的重量 for(int i=1;i<=n;i++) { cin>>v[i]>>w[i];//输入重量和他的价值 } for(int i=1;i<=n;i++)//j重量下,前i个物品的最大价值 for(int j=1;j<=m;j++) { if(j<v[j]) //如果能放进去,那么就更新数据 f[i][j]=f[i-1][j]; else //如果放不进去,那么就找前面的数的最大价值! f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); } cout<<f[n][m]<<endl;// return 0; }
时间: 2023-11-16 14:06:13 浏览: 61
使用include <iostream>时一定要加using namespace std
这段代码是经典的01背包问题的解法,思路正确,但是有一些细节可以进行优化:
1. 声明二维数组f[N][N],其中N可以开得更小,因为最大重量不一定会达到N。
2. 在输入每个物品的重量和价值时,可以使用cin快速读入,而不是使用scanf。
3. 在更新数据时,可以使用滚动数组的方法将二维数组f[N][N]优化成一维数组f[N],从而减少空间复杂度。
4. 在判断能否放入物品时,可以使用if语句替换掉if-else语句,从而减少分支判断的开销。
下面是优化后的代码:
```c++
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005; //将N改小,以减少空间复杂度
int n, m;
int f[N];
int main () {
cout << "请输入有几件物品,和最大重量:" << endl;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i]; //使用cin快速读入
}
for(int i = 1; i <= n; i++) {
for(int j = m; j >= v[i]; j--) { //使用滚动数组的方法优化空间
f[j] = max(f[j], f[j - v[i]] + w[i]); //使用if语句替换if-else语句
}
}
cout << f[m] << endl;
return 0;
}
```
阅读全文