多重背包

发表于 分类于 ， ，

简介

在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

其他背包问题