多重背包

简介

在0-1背包中,每个物品只有一个,要么拿,要么不拿;完全背包的每种物品的数量是无限的,可以重复装;而在多重背包中,物品可以重复装,但是每种物品都有着数量限制,此种物品装完后即使背包有容量也不可以再装了。


解法

设有以下几种物品:

物品(i) 重量(\(w_i\)) 价值(\(v_i\)) 数量(\(num_i\))
物品1 1 2 3
物品2 2 4 1
物品3 3 4 3
物品4 4 5 2

多重背包与完全背包的解法相似,只是多了一个限制条件,即物品数量有限。可以将物品展开当成0-1背包来计算,也可以按照多重背包的解法二来计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
w = [1, 2, 3, 4]
v = [2, 4, 4, 5]
num = [3, 1, 3, 2]

w_a = 9 # 背包容量
n = len(w)

dp = [[0] * (w_a + 1) for _ in range(n + 1)] # 初始化动态规划数组

for i in range(1, n + 1): # 状态转移
for j in range(1, w_a + 1):
dp[i][j] = dp[i - 1][j]
for k in range(1, min(j // w[i - 1], num[i - 1]) + 1): # 最大数量和最大容量中的最小值
dp[i][j] = max(dp[i - 1][j - k * w[i - 1]] + k * v[i - 1], dp[i][j])
# 最终结果
print(dp[-1][-1])
[out]: 15

# 状态转移结果
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 6, 6, 6, 6, 6, 6]
[0, 2, 4, 6, 8, 10, 10, 10, 10, 10]
[0, 2, 4, 6, 8, 10, 10, 12, 14, 14]
[0, 2, 4, 6, 8, 10, 10, 12, 14, 15]

END

其他背包问题