完全背包

发表于 分类于 ， ，

简介

在0-1背包中，每个物品只有一个，要么拿，要么不拿。完全背包与0-1背包的不同点在于，完全背包的每种物品的数量是无限的，可以重复装，也就是说只要背包容量够，每种物品可以选择不装、装一个、装两个......装n个。求这种情况下一定容量下的背包可以装下的物品的最大价值。依旧采用动态规划求解。

解法

设有以下几种物品：

物品(i) 重量(\(w_i\)) 价值(\(v_i\))
物品0 2 3
物品1 3 4
物品2 4 5
物品3 5 6
物品4 6 7

背包总容量(\(w_a\)​)为9，如何选择物品才能让背包的能够装的价值最大？

解法一

虽然物品有限，但是背包的容量是给定的，也就是说，对于每种物品，其最多可以装\(floor(w_a/w_i)\)​​个，因此我们可以把每种物品展开，对于展开后的物品，就可以当做0-1背包问题来解决：

物品(i) 重量(\(w_i\)) 价值(\(v_i\)) 可展开数量
物品0 2 3 9//2=4
物品1 3 4 9//3=3
物品2 4 5 9//4=2
物品3 5 6 9//5=1
物品4 6 7 9//6=1

展开后物品情况:

物品(i) 重量(\(w_i\)) 价值(\(v_i\))
物品0-1 2 3
物品0-2 2 3
物品0-3 2 3
物品0-4 2 3
物品1-1 3 4
物品1-2 3 4
物品1-3 3 4
物品2-1 4 5
物品2-2 4 5
物品3 5 6
物品4 6 7

如此一来，就可以当做0-1背包来求解了，但是这样做的话会大量消耗而外的空间时间复杂度。

解法二

在0-1背包中，我们用\(dp[i][j]\)​​来表示仅从前i个物品里面选择且背包总容量为j时物品的最大价值。对于0-1背包来说，第\(i\)个物品只有选或者不选两种情况，而完全背包面临着第\(i\)​个物品不选、选一个、选两个....等情况。因此状态转移方程改为如下:

\(dp[i][j] = max(dp[i][j-k*w_i]+v_i | 0<k<=j//w_a,dp[i-1][j])\)

此时，对于每一个\(dp[i][j]\)，需要比较装不同个\(w_a\)时的最大值，示例代码如下：

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
# 初始化重量、价值
w = list(range(2, 6))
v = list(range(3, 7))
n = len(w)

w_a = 9

# 初始化状态
dp = [[0] * (w_a + 1) for _ in range(n)]
# 转态初值设置
for i in range(w_a + 1):
    dp[0][i] = i // w[0] * v[0]

for i in range(1, n):
    for j in range(1, w_a + 1): # 重量需要取到w_a
        dp[i][j] = dp[i - 1][j] # 若不装
        for k in range(0, j // w[i] + 1): # 装不同个的最大值
            dp[i][j] = max(dp[i - 1][j - k * w[i]] + k * v[i], dp[i][j])
# 最终结果
print(dp[-1][w_a])
[out]: 13

转态转移结果
[0, 0, 3, 3, 6, 6, 9, 9, 12, 12]
[0, 0, 3, 4, 6, 7, 9, 10, 12, 13]
[0, 0, 3, 4, 6, 7, 9, 10, 12, 13]
[0, 0, 3, 4, 6, 7, 9, 10, 12, 13]

解法三

多重背包中当前装入第\(i\)​个物品的数量会影响之后此物品是否能再次装入背包，因此转态转移方程可以写成:

\(dp[i][j] = max(dp[i][j-w[i]]+v[i],dp[i-1][j])\)​

此状态方程与0-1背包的相似，不同点在于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
25
26
27
28
w = list(range(2, 6))
v = list(range(3, 7))
# 倒序，增加数据多样性
w.sort(reverse=True)
v.sort(reverse=True)
n = len(w)

w_a = 9

dp = [[0] * (w_a + 1) for _ in range(n)]

for i in range(w_a + 1):
    dp[0][i] = i // w[0] * v[0]

for i in range(1, n):
    for j in range(1, w_a + 1):
        dp[i][j] = dp[i - 1][j]
        if j - w[i] >= 0:
            dp[i][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
# 最终结果
print(dp[-1][w_a])
[out]:13

# 状态转移结果
[0, 0, 0, 0, 0, 6, 6, 6, 6, 6]
[0, 0, 0, 0, 5, 6, 6, 6, 10, 11]
[0, 0, 0, 4, 5, 6, 8, 9, 10, 12]
[0, 0, 3, 4, 6, 7, 9, 10, 12, 13]

END

其他背包问题