题目大意:
有 $N$ 件物品和一个容量是 $V$ 的背包,背包能承受的最大重量是 $M$。
每件物品只能用一次。体积是 $v_i$,重量是 $m_i$,价值是 $w_i$。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
解题方法:
我们会发现这里比01背包问题多了一个重量,所以我们只需要将 $f[i][j]$ 变成 $f[i][j][k]$ 就行了。
$$ 闫氏DP分析法 $$
- 状态表示——集合:$f[i][j][k]$ 表示考虑前 $i$ 个物品,且容量不超过 $j$,总重量不超过 $k$ 的集合下能获得的最大价值。
- 状态表示——属性:因为是求最大价值,故为 $max$。
- 状态计算——集合划分:考虑第 $i$ 个物品选不选。
- 不选或选不了(剩余时间不够 $j < v[i]$):$f[i - 1][j][k]$。
- 选:$f[i - 1][j - v1[i]][k - v2[i]] + w[i]$。首先你对第i个物品进行了你的抉择,所以前一维变成了 $i - 1$,接着因为使用了 $v1[i]$ 的体积,所以应该是$j - v[i]$,使用了 $v2[i]$ 的重量所以是 $k - v2[i]$。 最后你要把它带来的价值加上,所以要加上 $w[i]$。
对应的,当然也可以像01背包一样舍去第一维。
完整代码,时间复杂度:$O(nmk)$
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, v, m;
int f[N][N];
int main() {
cin >> n >> v >> m;
for (int i = 1; i <= n; i ++ ) {
int a, b, w;
cin >> a >> b >> w;
for (int j = v; j >= a; j -- ) {
for (int k = m; k >= b; k -- ) {
f[j][k] = max(f[j][k], f[j - a][k - b] + w);
}
}
}
cout << f[v][m] << endl;
}