题目大意:
题目相当于要你选若干个物品,让他们的体积不超过背包容量,且价值最大。
解题方法:
$$闫氏DP分析法$$
- 状态表示——集合:$f[i][j]$ 表示考虑前 $i$ 个物品,且总体积不超过 $j$ 的集合下能获得的最大价值。
- 状态表示——属性:因为是求最大价值,故为 $max$。
- 状态计算——集合划分:考虑第 $i$ 个选不选。
- 不选或选不了(剩余体积不够 $j < v[i]$):$f[i - 1][j]$。
- 选:$f[i - 1][j - v[i]] + w[i]$。首先你对第$i$个物品进行了你的抉择,所以前一维变成了$i - 1$,接着因为使用了$v[i]$的体积,所以应该是$j - v[i]$,最后你要把它带来的价值加上,所以要加上$w[i]$。
那么代码里就这么写:
f[i][j] = f[i - 1][j]; //不选,这种情况绝对可以选择
if (j >= v[i]) //体积必须足够,否则不能放置
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //选,花费v[i]的体积,获得w[i]的价值
完整代码,时间复杂度:$O(nm)$
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][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 = 1; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m];
return 0;
}
然后我想啊想,那第一维只考虑到 $i - 1$ 能不能优化呢?
能!
我们用滚动数组优化,f[1][j]放到f[1][j],f[2][j]放到f[0][j],f[3][j] 可以覆盖f[1][j],也就是放到f[i & 1][j]上...
这里可以直接把每个用到 $f$ 的位置 &1
就可以了。&1
就相当于%2
。
另:之后的问题我就不写滚动数组了,滚动数组只是能优化空间,不在空间不足的情况下无需使用。
滚动数组也就相当于反复覆盖之前无用的空间而已
也就相当于:
f[i][j] = f[i & 1][j]
举个栗子:
f[1][j] = f[1][j]
f[2][j] = f[0][j]
f[3][j] = f[1][j]
f[4][j] = f[0][j]
然而并不会影响结果,因为每次覆盖的都是没有用的。
完整代码,时间复杂度:$O(nm)$
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[2][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 = 1; j <= m; j ++ ) {
f[i & 1][j] = f[i - 1 & 1][j];
if (j >= v[i]) f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - v[i]] + w[i]);
}
cout << f[n & 1][m];
return 0;
}
现在我要得寸进尺,能不能把第一维直接省去呢?
能!!!
但不能像之前直接更改了,因为更新 $f[j]$ 的已经被更新过,不能再次更新,需要将体积倒着枚举,这样的话:
f[j]
没有被更新过,而且f[j - v[i]]
由于j - v[i]
比j
小,没有被遍历过,也就是 i - 1
更新的东西,这样就可以了。
完整代码,时间复杂度:$O(nm)$
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[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 -- ) { //体积小于v[i]的f不会被更新,所以只需遍历到v[i]
f[j] = max(f[j], f[j - v[i]] + w[i]); //现在的f[j]就是f[i - 1][j],并且可以选择i
//而f[j - v[i]]没有被更新,所以就又变成了f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[m];
return 0;
}
–很清晰–