有一个质量上限为 $m$ 的背包和 $n$ 个物品。物品分三类,第一类物品有取的数
量限制,第二类物品只能取一个,第三类物品可以无限取。
第 $i$ 个物品的类别为 $tp[i] (tp[i] \in [1,2,3])$ 质量为 $w[i]$,价值为 $c[i]$,如果 $tp[i]=1$,还会有一个数表示这种物品最多只能取 $a[i]$ 个。
求这个背包可以装下的最大价值。
$m \leq 1000, n \leq 100, w[i],c[i] \leq 1000, a[i] < 10, 1 \leq tp[i] \leq 3$
注意: $c_i$ 可能为 $0$ 。
试补全程序。
#include <iostream>
using namespace std;
int n, m, ans;
int f[100], a[101], tp[101], w[101], c[101];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; ++i) {
cin >> tp[i] >> w[i] >> c[i];
if (tp[i] == 1) cin >> a[i];
}
f[0] = 0;
for (int i = 1; i <= m; ++i)
f[i] = ___(1)___;
for (int i = 1; i <= n; ++i) {
if (tp[i] == 1) {
for (int j = 1; j <= a[i]; ++j)
for (int v = m; v >= w[i]; --v)
f[v] = max(f[v], ___(5)___);
} else if (tp[i] == ___(2)___) {
for (int v = m; v >= ___(3)___; --v)
f[v] = max(f[v], ___(5)___);
} else {
for (___(4)___)
f[v] = max(f[v], ___(5)___);
}
}
printf("%d", f[m]);
return 0;
}
说明:(5) 处有 $3$ 个,这 $3$ 处填的代码是一样的。
1. C。
2. A。
3. D。
4. C。
5. C。
可以看出,题目实际上是由三个不同的背包混合而成的,所以我们的代码也是三种转移混合而成的。对于有限次物品的背包,我们直接做 $a[i]$ 次 $01$ 背包,也就是假设有 $a[i]$ 个物品价值相同,数量只有 $1$ ;对于无限数量物品和只有一件的物品则分别采取完全背包和 $014 背包的方式更新。