一、朴素写法:二维DP数组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N]; //存放物品体积
int w[N]; //存放物品价值
int f[N][N]; //f[i][j]:前i个物品在j体积下的最大价值
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i ++) cin>>v[i]>>w[i];
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++){
//当前背包容量装不下第i个物品,则直接等于前i个物品在j体积下的最大价值
if(j - v[i] < 0)
f[i][j] = f[i - 1][j];
else
//因为f[i][j]表示的是前i个物品在j体积下的最大值
//容量足够的时候,需要考虑物品放或者不放
//如果不放,则前i个物品在j体积下的价值最大值即为前i-1个物品在j体积下的价值最大值
//如果放,(有可能放下该物品的同时,前面的物品可能不再适合放入背包)
//故要保证当前为最优解,需保证在加入该物品的同时,其前面的物品也是最优解
//前面物品的价值最大值为前i-1个物品在体积为j-v[i](要保证放入v[i]时总容量不能超过背包容量上限)的价值最大值
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
/*for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m;j ++)
cout<<f[i][j]<<" ";
puts("");
}*/
cout<<f[n][m]<<endl;
return 0;
}
二、一维DP数组
理解:之所以倒着遍历j,是因为在外层循环第i轮时,如果使用正序,则当f[j]=f[j-1]时是使用的本轮(第i轮-外层循环)的刚更新的状态,而我们的算法是需要用到上一层的状态。算法倒着遍历,且j始终>=v[i],这就使得每一次对j进行遍历时,上轮的数据得以保存,不会被冲刷掉(可以手动模拟一下)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int f[N];
int v[N], w[N];
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i ++ ) cin>>v[i]>>w[i];
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]);
}
}
cout<<f[m]<<endl;
return 0;
}
对输入进行优化后的代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int f[N];
int v[N], w[N];
int main(){
cin>>n>>m;
//for(int i = 1; i <= n; i ++ ) cin>>v[i]>>w[i];
for(int i = 1; i <= n; i ++){
int v, w;
cin>>v>>w;
for(int j = m; j >= v; j --){
f[j] = max(f[j], f[j - v] + w);
}
}
cout<<f[m]<<endl;
return 0;
}