背包问题练习（三）——多重背包问题
文章目录
多重背包问题讲解视频：多重背包两种解法硬头皮算和二进制优化 动态规划
题目来自洛谷题单背包问题
樱花
题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了 $n$ 棵樱花树，每棵都有美学值 $C_i(0 \le C_i \le 200)$。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 $P_i(0 \le P_i \le 100)$ 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 $T_i(0 \le T_i \le 100)$。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。
输入格式
共 $n+1$行：
第 $1$ 行：现在时间 $T_s$（几时：几分），去上学的时间 $T_e$（几时：几分），爱与愁大神院子里有几棵樱花树 $n$。这里的 $T_s$，$T_e$ 格式为：hh:mm，其中 $0 \leq hh \leq 23$，$0 \leq mm \leq 59$，且 $hh,mm,n$ 均为正整数。
第 $2$ 行到第 $n+1$ 行，每行三个正整数：看完第 $i$ 棵树的耗费时间 $T_i$，第 $i$ 棵树的美学值 $C_i$，看第 $i$ 棵树的次数 $P_i$（$P_i=0$ 表示无数次，$P_i$ 是其他数字表示最多可看的次数 $P_i$）。
输出格式
只有一个整数，表示最大美学值。
样例 #1
样例输入 #1
16:50 7:00 3
22 1 0
33 3 1
44 5 4
样例输出 #1
111
提示
$100%$ 数据：$T_e-T_s \leq 1000$（即开始时间距离结束时间不超过 $1000$ 分钟），$n \leq 10000$。保证 $T_e,T_s$ 为同一天内的时间。
样例解释：赏第一棵樱花树一次，赏第三棵樱花树 $2$ 次。
题解
一个背包问题中完全背包与多重背包的混合题型。将多重背包使用二进制优化转化为 0-1 背包问题后，只要对不同物品使用不同的状态转移方程即可。
1def main():
2 Ts, Te, n = input().split(" ")
3 Tsh, Tsm = map(int, Ts.split(":"))
4 Teh, Tem = map(int, Te.split(":"))
5 T = Teh * 60 + Tem - Tsh * 60 - Tsm
6 n = int(n)
7
8 t, c, p = [0], [0], [0]
9 for _ in range(n):
10 ti, ci, pi = map(int, input().split(" "))
11 if pi:
12 k = 1
13 while k <= pi:
14 t.append(ti * k)
15 c.append(ci * k)
16 p.append(0)
17 pi -= k
18 k *= 2
19 if pi:
20 t.append(ti * pi)
21 c.append(ci * pi)
22 p.append(0)
23 else:
24 t.append(ti)
25 c.append(ci)
26 p.append(1)
27
28 dp = [0 for _ in range(T + 1)]
29 for i in range(1, len(p)):
30 if p[i]:
31 for j in range(t[i], T + 1):
32 dp[j] = max(dp[j], dp[j - t[i]] + c[i])
33 else:
34 for j in reversed(range(t[i], T + 1)):
35 dp[j] = max(dp[j], dp[j - t[i]] + c[i])
36 print(dp[-1])
37
38
39if __name__ == "__main__":
40 main()
这段代码提交上去后，有两个测试点超时。观察代码后发现，程序可以在处理输入数据时同时完成对 dp 数组的遍历来减少循环次数。
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6int main() {
7 int Tsh, Tsm, Teh, Tem, n;
8 char c;
9 cin >> Tsh >> c >> Tsm >> Teh >> c >> Tem >> n;
10 int T = Teh * 60 + Tem - Tsh * 60 - Tsm;
11
12 int dp[1001] = { 0 };
13 while (n--) {
14 int Ti, Ci, Pi;
15 cin >> Ti >> Ci >> Pi;
16 if (Pi) {
17 int k = 1;
18 while (k <= Pi) {
19 for (int i = T; i >= Ti * k; i--) {
20 dp[i] = max(dp[i], dp[i - Ti * k] + Ci * k);
21 }
22 Pi -= k;
23 k *= 2;
24 }
25 if (Pi) {
26 for (int i = T; i >= Ti * Pi; i--) {
27 dp[i] = max(dp[i], dp[i - Ti * Pi] + Ci * Pi);
28 }
29 }
30 }
31 else {
32 for (int i = Ti; i <= T; i++) {
33 dp[i] = max(dp[i], dp[i - Ti] + Ci);
34 }
35 }
36 }
37 cout << dp[T];
38 return 0;
39}
用 C++ 还是因为 Python 过不了。
[SNOI2017] 英雄联盟
题目描述
正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。
现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！
小皮球只会玩 $\text{N}$ 个英雄，因此，他也只准备给这 $\text{N}$ 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。
这 $\text{N}$ 个英雄中，第 $\text{i}$ 个英雄有 $K_i$ 款皮肤，价格是每款 $C_i$ Q 币（同一个英雄的皮肤价格相同）。
为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。
比如，小皮球共有 5 个英雄，这 5 个英雄分别有 $\text{0,0,3,2,4}$ 款皮肤，那么，小皮球就有 $3 \times 2 \times 4 = 24$ 种展示的策略。
现在，小皮球希望自己的展示策略能够至少达到 $\text{M}$ 种，请问，小皮球至少要花多少钱呢？
输入格式
第一行，两个整数 $\text{N,M}$。
第二行，$\text{N}$ 个整数，表示每个英雄的皮肤数量 $K_i$。
第三行，$\text{N}$ 个整数，表示每个英雄皮肤的价格 $C_i$。
输出格式
一个整数，表示小皮球达到目标最少的花费。
样例 #1
样例输入 #1
13 24
24 4 4
32 2 2
样例输出 #1
118
提示
样例解释
每一个英雄都只有4款皮肤，每款皮肤2 Q币，那么每个英雄买3款皮肤，$3 \times 3 \times 3 \ge 24$，共花费 $6 \times 3$ Q币。
数据范围
共 10 组数据，第 $\text{i}$ 组数据满足：$\text{N} \le \max(5, \log_2^4i)$
$\text{100}%$ 的数据：$\text{M} \le 10^{17}, 1 \le K_i \le 10, 1 \le C_i \le 199$。保证有解。
题解
这道题虽然还一道多重背包问题，但是这道题不能用二进制优化。需要使用三重循环，多定义一层 k 的循环，来表示当前英雄购买的皮肤数。不难发现状态转移方程为 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * C[i]] * k), k <= K[i], j >= k * C[i]。当然这里的 dp[i][j] 已经是从 dp[i - 1][j] 的状态复制来的。
这道题另一个坑是，这道题实际上是要求满足 dp[N][j] >= M 时 j 的最小值，因此 dp 数组的宽度应该是可能的开销的最大值，即 $\sum_{i=1}^{N} K_i C_i$。根据上述信息写出程序：
1def main():
2 N, M = map(int, input().strip().split(" "))
3 K = [0] + list(map(int, input().strip().split(" ")))
4 C = [0] + list(map(int, input().strip().split(" ")))
5 max_cost = sum(map(lambda x: x[0] * x[1], zip(K, C)))
6
7 dp = [[1 for _ in range(max_cost + 1)] for _ in range(N + 1)]
8 for i in range(1, N + 1):
9 for j in range(1, max_cost + 1):
10 dp[i][j] = dp[i - 1][j]
11 for k in range(0, K[i] + 1):
12 if j < k * C[i]:
13 break
14 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * C[i]] * k)
15
16 for i in range(len(dp[-1])):
17 if dp[-1][i] >= M:
18 print(i)
19 break
20
21
22if __name__ == "__main__":
23 main()
随后优化代码：
1def main():
2 N, M = map(int, input().strip().split(" "))
3 K = [0] + list(map(int, input().strip().split(" ")))
4 C = [0] + list(map(int, input().strip().split(" ")))
5 max_cost = sum(map(lambda x: x[0] * x[1], zip(K, C)))
6
7 dp = [1 for _ in range(max_cost + 1)]
8 for i in range(1, N + 1):
9 for j in reversed(range(1, max_cost + 1)):
10 for k in range(0, min(K[i], j // C[i]) + 1):
11 dp[j] = max(dp[j], dp[j - k * C[i]] * k)
12
13 for i in range(max_cost + 1):
14 if dp[i] >= M:
15 print(i)
16 return
17
18
19if __name__ == "__main__":
20 main()
Python 果然不孚众望，又双叒叕超时了。🤯
拼尽全力无法 AC，受不了了！传 C++！
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6int main() {
7 long long int N, M, K[123] = { 0 }, C[123] = { 0 }, dp[100001] = {1}, max_cost = 0;
8 cin >> N >> M;
9 for (int i = 1; i <= N; i++) {
10 cin >> K[i];
11 }
12 for (int i = 1; i <= N; i++) {
13 cin >> C[i];
14 max_cost += C[i] * K[i];
15 }
16
17 for (int i = 1; i <= N; i++) {
18 for (int j = max_cost; j >= 1; j--) {
19 for (int k = 0; k <= min(K[i], j / C[i]); k++) {
20 dp[j] = max(dp[j], dp[j - k * C[i]] * k);
21 }
22 }
23 }
24
25 for (int i = 1; i <= max_cost; i++) {
26 if (dp[i] >= M) {
27 cout << i;
28 return 0;
29 }
30 }
31}
[NOIP1996 提高组] 砝码称重
题目描述
设有 $1\mathrm{g}$、$2\mathrm{g}$、$3\mathrm{g}$、$5\mathrm{g}$、$10\mathrm{g}$、$20\mathrm{g}$ 的砝码各若干枚（其总重 $ \le 1000$），可以表示成多少种重量？
输入格式
输入方式：$a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6$
（表示 $1\mathrm{g}$ 砝码有 $a_1$ 个，$2\mathrm{g}$ 砝码有 $a_2$ 个，$\dots$，$20\mathrm{g}$ 砝码有 $a_6$ 个）
输出格式
输出方式：Total=N
（$N$ 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
样例 #1
样例输入 #1
11 1 0 0 0 0
样例输出 #1
1Total=3
提示
【题目来源】
NOIP 1996 提高组第四题
题解
这道题最容易想到的就是暴力枚举，当然也同样容易想到暴力枚举大概率超时。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <bitset>
5
6int main() {
7 int a, b, c, d, e, f;
8 int i, j, k, l, m, n;
9 scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
10 std::bitset<1001> weight;
11 for (i = 0; i <= a; i++) {
12 for (j = 0; j <= b; j++) {
13 for (k = 0; k <= c; k++) {
14 for (l = 0; l <= d; l++) {
15 for (m = 0; m <= e; m++) {
16 for (n = 0; n <= f; n++) {
17 weight.set(i + j * 2 + k * 3 + l * 5 + m * 10 + n * 20);
18 }
19 }
20 }
21 }
22 }
23 }
24 printf("Total=%d", weight.count() - 1);
25 return 0;
26}
过了！？这么离谱的做法也能过？好吧，使用枚举法，C++ 在某个测试点上最长花了 842ms。而下面这个方法，即使是用 Python，最长也只需要 52ms。
这道题也可以看作多重背包问题的变种。一共有 6 种物品，每种物品的价值和重量相等，分别是 1, 2, 3, 5, 10, 20。首先求出这些物品可能的最大价值 max_weight，随后计算当背包容量为 1 到 max_weight 中的任意值时，背包所能装的最大价值时多少。当背包容量和最大价值相等时，说明用已有的砝码能够凑出该重量。此时问题就被转换成了一个经典的多重背包问题。
1def main():
2 count = tuple(map(int, [0] + input().split(" ")))
3 weight = (0, 1, 2, 3, 5, 10, 20)
4 max_weight = sum(map(lambda x: x[0] * x[1], zip(weight, count)))
5
6 dp = [0 for _ in range(max_weight + 1)]
7 for i in range(1, 7):
8 for j in reversed(range(weight[i], max_weight + 1)):
9 for k in range(0, min(count[i], j // weight[i]) + 1):
10 dp[j] = max(dp[j], dp[j - weight[i] * k] + weight[i] * k)
11
12 res = 0
13 for i in range(1, max_weight + 1):
14 if i == dp[i]:
15 res += 1
16 print(f"Total={res}")
17
18
19if __name__ == "__main__":
20 main()
AC！
这类问题也被归类为“可行性问题”。
宝物筛选
题目描述
终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。
这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。
小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
输入格式
第一行为一个整数 $n$ 和 $W$，分别表示宝物种数和采集车的最大载重。
接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。
输出格式
输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。
样例 #1
样例输入 #1
14 20
23 9 3
35 9 1
49 4 2
58 1 3
样例输出 #1
147
提示
对于 $30%$ 的数据，$n\leq \sum m_i\leq 10^4$，$0\le W\leq 10^3$。
对于 $100%$ 的数据，$n\leq \sum m_i \leq 10^5$，$0\le W\leq 4\times 10^4$，$1\leq n\le 100$。
题解
简单的多重背包问题，但是需要优化，否则会超时。下面的是使用二进制优化的代码：
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <algorithm>
5
6int main() {
7 int N, W, vi, wi, mi, dp[40001] = { 0 }, i, j, k;
8 scanf("%d%d", &N, &W);
9
10 for (i = 1; i <= N; i++) {
11 scanf("%d%d%d", &vi, &wi, &mi);
12 k = 1;
13
14 while (mi >= k) {
15 for (j = W; j >= wi * k; j--) {
16 dp[j] = std::max(dp[j], dp[j - k * wi] + k * vi);
17 }
18 mi -= k;
19 k *= 2;
20 }
21 if (mi > 0) {
22 for (j = W; j >= wi * mi; j--) {
23 dp[j] = std::max(dp[j], dp[j - mi * wi] + mi * vi);
24 }
25 }
26 }
27
28 printf("%d", dp[W]);
29 return 0;
30}
旅行商的背包
题目描述
小 S 坚信任何问题都可以在多项式时间内解决，于是他准备亲自去当一回旅行商。在出发之前，他购进了一些物品。这些物品共有 $n$ 种，第 $i$ 种体积为 $V_i$，价值为 $W_i$，共有 $D_i$ 件。他的背包体积是 $C$。怎样装才能获得尽量多的收益呢？作为一名大神犇，他轻而易举的解决了这个问题。
然而，就在他出发前，他又收到了一批奇货。这些货共有 $m$ 件，第 $i$ 件的价值 $Y_i$ 与分配的体积 $X_i$ 之间的关系为：$Y_i=a_iX_i^2+b_iX_i+c_i$。这是件好事，但小 S 却不知道怎么处理了，于是他找到了一位超级神犇（也就是你），请你帮他解决这个问题。
输入格式
第一行三个数 $n,m,C$，如题中所述；
以下 $n$ 行，每行有三个数 $V_i,W_i,D_i$，如题中所述；
以下 $m$ 行，每行有三个数 $a_i,b_i,c_i$，如题中所述。
输出格式
仅一行，为最大的价值。
样例 #1
样例输入 #1
12 1 10
21 2 3
33 4 1
4-1 8 -16
样例输出 #1
110
提示
样例解释
前两种物品全部选走，最后一个奇货分给 $4$ 的体积，收益为$2 \times 3+4 \times 1+(-1) \times 16+8 \times 4+(-16)=10$。
限制与约定
对于 $100%$ 的数据，$1 \le n \le 10^4$，$1 \le m \le 5$，$1 \le C \le 10^4$，$ 1 \le W_i,V_i,D_i \le 1000$，$-1000 \le a_i,b_i,c_i \le 1000$。
题解
这道题可以分为两部分：第一部分普通物品按照多重背包问题解决，第二部分奇货通过枚举计算。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <algorithm>
5
6int main() {
7 int N, M, C, va, wb, dc, yi;
8 int i, j, k;
9 long long dp[10005] = { 0 };
10
11 scanf("%d%d%d", &N, &M, &C);
12 for (i = 0; i < N; i++) {
13 scanf("%d%d%d", &va, &wb, &dc);
14 if (dc * va > C) {
15 for (j = va; j <= C; j++) {
16 dp[j] = std::max(dp[j], dp[j - va] + wb);
17 }
18 }
19
20 else {
21 k = 1;
22 while (dc >= k) {
23 for (j = C; j >= va * k; j--) {
24 dp[j] = std::max(dp[j], dp[j - va * k] + 1ll * wb * k);
25 }
26 dc -= k;
27 k <<= 1;
28 }
29
30 if (dc > 0) {
31 for (j = C; j >= va * dc; j--) {
32 dp[j] = std::max(dp[j], dp[j - va * dc] + 1ll * wb * dc);
33 }
34 }
35 }
36 }
37
38 for (i = 0; i < M; i++) {
39 scanf("%d%d%d", &va, &wb, &dc);
40 for (j = C; j >= 0; j--) {
41 for (k = 0; k <= j; k++) {
42 dp[j] = std::max(dp[j], dp[j - k] + 1ll * va * k * k + wb * k + dc);
43 }
44 }
45 }
46
47 printf("%lld", dp[C]);
48 return 0;
49}
中间做了一个 dc * va > C 的判断，即当某个普通物品的总体积超过背包体积时，就当作完全背包问题解决（我猜测没有测试点的数据会使程序进入这个判断里，因为我其中一次提交时误将 j <= C 写成 j <= dc 但结果没有影响）。其余多重背包的部分必须优化，否则会超时。另外 dp 数组必须定义成 long long 型，运算时加到数组里的元素也要先乘 1ll 不然有一个测试点死活过不了。