共42道题,当前是第31

初赛真题

有一个质量上限为 $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 背包的方式更新。

Question

1. (1) 处应填 [ ]。

2. (2) 处应填 [ ]。

3. (3) 处应填 [ ]。

4. (4) 处应填 [ ]。

5. (5) 处应填 [ ]。

陈伦制作 版权所无 粤ICP备16127491号-1