背包问题——分组背包问题
文章目录
题目来自洛谷题单背包问题
分组背包中的每一组都只能选择一种物品。从外向内的遍历顺序依次是：组号 $i$、当前背包重量 $j$ 和当前组内物品 $g_i$。
P1757 通天之分组背包
题目背景
直达通天路·小 A 历险记第二篇
题目描述
自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入格式
两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。
接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。
输出格式
一个数，最大的利用价值。
输入输出样例 #1
输入 #1
145 3
210 10 1
310 5 1
450 400 2
输出 #1
110
说明/提示
$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。
题解
分组背包模板题。
1from collections import defaultdict
2
3m, n = map(int, input().strip().split())
4groups = defaultdict(list)
5for _ in range(n):
6 a, b, c = map(int, input().strip().split())
7 groups[c].append((a, b))
8
9dp = [0] * (m + 1)
10for i in groups.keys():
11 for j in range(0, m + 1)[::-1]:
12 for a, b in groups[i]:
13 dp[j] = max(dp[j], dp[j - a] + b)
14
15print(dp[-1])
P5322 [BJOI2019] 排兵布阵
题目描述
小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。
如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。
现在小 C 即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 $s$ 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。
由于答案可能不唯一，你只需要输出小 C 总分的最大值。
输入格式
输入第一行包含三个正整数 $s,n,m$，分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。
接下来 $s$ 行，每行 $n$ 个非负整数，表示一名玩家的策略，其中第 $i$ 个数 $a_i$ 表示这名玩家向第 $i$ 座城堡派遣的士兵数。
输出格式
输出一行一个非负整数，表示小 C 获得的最大得分。
输入输出样例 #1
输入 #1
11 3 10
22 2 6
输出 #1
13
输入输出样例 #2
输入 #2
12 3 10
22 2 6
30 0 0
输出 #2
18
说明/提示
样例1解释：
小 C 的最佳策略为向第 $1$ 座城堡和第 $2$ 座城堡各派遣 $5$ 名士兵。
样例2解释：
小 C 的最佳策略之一为向第 $1$ 座城堡派遣 $2$ 名士兵，向第 $2$ 座城堡派遣 $5$ 名士兵，向第 $3$ 座城堡派遣 $1$ 名士兵。
数据范围：
对于 $10%$ 的数据： $s=1,n \le 3,m \le 10$
对于 $20%$ 的数据： $s=1,n \le 10,m \le 100$
对于 $40%$ 的数据： $n\le 10,m\le 100$
对于另外 $20%$ 的数据： $s=1$
对于 $100%$ 的数据：
$1\le s \le 100$
$1\le n \le 100$
$1\le m \le 20000$
对于每名玩家 $a_i \ge 0$，$\sum\limits_{i=1}^n a_i \le m$
题解
如果不是在题单中刷到这道题，我还真不一定能想到这道题要用分组背包模型解决。
题目中的己方士兵人数是背包上限，每一座城都是一组，同一组里不同物品的重量是其他玩家放置的兵力乘二加一，而获得的价值是城堡编号 $i$ 乘上战败玩家的数量 $k$。因此可以将每座城堡中的兵力按照从小到大排序，小 C 在第 $i$ 座城堡每打赢一次，他就能够获得 $i$ 分，打赢前 $k$ 名玩家就能获得 $i\times k$ 分。因此可以知道状态转移方程为 dp[j] = max(dp[j], dp[j - groups[i][k] * 2 - 1] + i * k)。其中 groups[i][k] 表示防守第 $i$ 个城堡，按照兵力从小到大排序为 $k$ 的玩家的兵力，即一组物品中的第 $k$ 个物品。
1s, n, m = map(int, input().strip().split())
2groups = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
3for i in range(1, s + 1):
4 si = tuple(map(int, input().strip().split()))
5 for j in range(1, n + 1):
6 groups[j][i] = si[j - 1]
7
8for i in range(1, n + 1):
9 groups[i].sort()
10
11dp = [0 for _ in range(m + 1)]
12for i in range(1, n + 1):
13 for j in range(0, m + 1)[::-1]:
14 for k in range(1, s + 1):
15 if groups[i][k] * 2 < j:
16 dp[j] = max(dp[j], dp[j - groups[i][k] * 2 - 1] + i * k)
17
18print(dp[m])
可惜 PyPy3 也拯救不了 $O(snm)$ 的时间复杂度，所以还是得交 C++。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <algorithm>
4#include <cstdio>
5
6using namespace std;
7
8int s, n, m;
9int groups[105][105];
10int dp[20005];
11
12int main() {
13 scanf("%d%d%d", &s, &n, &m);
14 for (int i = 1; i <= s; i++) {
15 for (int j = 1; j <= n; j++) {
16 scanf("%d", &groups[j][i]);
17 }
18 }
19
20 for (int i = 1; i <= n; i++) {
21 sort(groups[i] + 1, groups[i] + 1 + s);
22 }
23
24 for (int i = 1; i <= n; i++) {
25 for (int j = m; j >= 0; j--) {
26 for (int k = 1; k <= s; k++) {
27 if (j > groups[i][k] * 2) {
28 dp[j] = max(dp[j], dp[j - groups[i][k] * 2 - 1] + k * i);
29 }
30 }
31 }
32 }
33
34 printf("%d\n", dp[m]);
35}