分组背包
问题：每一组当中的物品只能选一个。
方法：在0/1背包的基础上，在每一组中遍历所有物品。
题目
1
2
3
4
5
6
7
8
9
10
| [输入描述] 第一行是整数 n 和 C，分别表示物品种数和背包的最大容量。接下来 n 行，每行三个整数 wi、ci、mi，分别表示第i个物品的价值、体积、数量。
[输出描述] 输出一个整数，表示背包不超载的情况下装入物品的最大价值
输入
4 20
3 9 3
5 9 1
9 4 2
8 1 3
输出
47
|
方法
方法一：转换为0/1问题
将每一个物品都看作是一种物品。
方法二：直接DP
其实也是转换为0/1问题，只不过在每一种（第i种）物品的时候，遍历他的个数。
前两种方法都会超时。
方法三：二进制拆分优化
例如第i个物品有25个（mi=25），那么这种物品的拿取情况就有26种。
用二进制的思想，可以将26拆分成1+2+4+8+10，也就是将26个单个的第i种物品，看成1个、2个、4个、8个、10个第i种物品，这5种“新物品”的组合就能有满足之前的26种情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
n, c = map(int, input().split())
W = [0]
C = [0]
M = [0]
for _ in range(n):
wi, ci, mi = map(int, input().split())
j = 1
t = j
while t < mi:
W.append(wi * j)
C.append(ci * j)
j <<= 1
t += j
else:
t = mi - (t - j)
W.append(wi * t)
C.append(ci * t)
dp = [0] * (c + 1)
for i in range(1, len(W)):
for j in range(c, C[i] - 1, -1):
dp[j] = max(dp[j], dp[j - C[i]] + W[i])
print(dp[-1])
|
二进制那块有点奇怪。。
方法四：单调队列
