完全背包

简介

在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\ast w_i]+v_i|0<k<=j//w_a,dp[i-1][j])$

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

# 初始化重量、价值
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背包是从前一个物品转移，完全背包是从当前物品转移。依据状态方程可以写出示例代码：

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

其他背包问题