题目描述
经典0-1背包问题
算法1:二维dp
状态变量:使用两个状态的动态规划,f[i][j],其物理意义为:对于前i个物体(即第一,第二,…第i个物体),使用背包体积为恰好j时,其最大的价值。
转移方程:f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])。第一项表示第i个物品不选,第二项表示第i个物品选
最终结果:max(f[n][~])
c++代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N]; //dp数组,两个状态,f[i][j]表示取到第i个,背包容量已用了j,的最大价值
int main(int argc, char** argv)
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; //记录v1, v2, ..., vn
for (int i = 1; i <= n; i++) //取到第n个物品为止
{
for (int j = 0; j <= m; j++) //用完背包容量为止
{
f[i][j] = f[i-1][j]; //不把两个情况合在一起写,防止不赋值的情况
if (j >= v[i])
f[i][j] = max(f[i-1][j-v[i]] + w[i], f[i][j]);
}
}
int ret = 0;
for (int i = 0; i <= m; i++) ret = max(ret, f[n][i]);
cout << ret << endl;
return 0;
}
算法2:一维dp
状态变量:f[j]表示使用体积恰好为j的时候,可以装下的最大价值
转移方程:f[j] = max(f[j], f[j-v[i]] + w[i]),第一项式子表示第j个物品不取,第二项式子表示第j个物品取
更新方式:但是对于f[j-v[i]]项,我们希望它在计算f[j]的时候在这一轮没有更新过。如果更新过,那么我们的代码在二维上是f[i][j] = max(f[i][j-v[i]] + w[i], ~),而这是不对的。因此我们要从大往小遍历,而不是从小往大
最终结果:max(f[j])。但是这里出现一个问题,如果我们仅把f[0]初始化为0,其他为-INF,那么f[m]为必定从f[0]转移而来,也就是;而如果把f都初始化为0,那么f[m]可能从其他f[k]中转移而来,此时其意义表示体积<=k的时候的最大价值
c++代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N]; //dp数组,f[j]表示体积是j情况下,的最大价值
int main(int argc, char** argv)
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; //记录v1, v2, ..., vn
for (int i = 1; i <= n; i++) //取到第n个物品为止
{
for (int j = m; j >= v[i]; j--) //用完背包容量为止
{
f[j] = max(f[j-v[i]] + w[i], f[j]);
/*
1. 总体状态更新的逻辑是:
只取第一个物品,f数组更新一次;
取第一第二个物品,f数组更新一次;
取第一第二第三个物品,f数组更新一次;
...
直到取到全部物品,f数组更新一次后结束
f数组的每一次更新,用f[i]表示背包容量恰好用到i的时候,能装下的最大价值
*/
}
}
cout << f[m] << endl;
return 0;
}