本文介绍了背包问题系列，主要包括：
【1】 01-背包及其应用
【2】完全背包及其应用
【3】多重背包
【1】01-背包及其应用：
1.1、01-背包问题描述：
有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。如：
| 物品 i | 重量 w | 价值 v |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
| 4 | 5 | 6 |
其中 N = 4，C = 8， 则最大价值为 10（即把物品 2 和 4 放入背包）。
1.2、01-背包解题思路：
01-背包问题适合用动态规划求解，用 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中的最大价值，因此此问题变成一个填表问题。如上述例子，dp[4][8] 就是最后的答案。
关键是找到状态转移方程。假设现在要计算 dp[i][j]，那么分为两种情况：
- 如果当前容量 j 小于第 i 件物品的重量（j < w[i]），则说明第 i 件物品肯定无法放入背包，那么此背包还是只有前 i-1 个物品，即
dp[i][j] = dp[i-1][j]。 - 如果当前容量 j 大于等于第 i 件物品的重量（j ≥ w[i]），则说明第 i 件物品有放入背包的基本条件。那么到底能不能放要取决于第 i 件物品的加入能否使得总价值最大。如果不能最大化总价值，那么还是
dp[i][j] = dp[i-1][j]，表示不放入第 i 件物品；如果可以最大化总价值，那么dp[i][j] = dp[i-1][j-w[i]] + v[i]，这里的dp[i-1][j-w[i]]为装入第 i 件物品之前的状态。
1.3、01-背包Python3 实现：
class Solution:
def knapsack01(self, N, w, v, C):
'''
@param N: int, 物品总数
@param w: List, 物品重量
@param v: List, 物品价值
@param C: int, 背包容量
'''
dp = [[0] * (C+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, C+1):
if j < w[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
return dp[-1][-1]
N = 4
w = [2,3,4,5]
v = [3,4,5,6]
C = 8
print(Solution().knapsack01(N, w, v, C)) # 10
注意：如果 j < w[i-1]，更新 dp[i][j] = dp[i-1][j] 是有必要的，比如下面的 dp[3][6] 的更新，就要用到 dp[2][2] 的结果。而 dp[2][2] 就是在 j < w[i-1] 的情况下使用 dp[2][2] = dp[1][2] 得到的：
之所以要强调这个点，是看到网上有人写代码直接写成如下形式：
for i in range(1, N + 1):
for j in range(w[i-1], C+1):
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
这种直接省略了 j < w[i-1] 的情况。这是错误的！！！
1.4、01-背包空间优化：
更进一步发现，每一次 dp[i][j] 的改变只与 dp[i-1][x] { x : 1...j } 有关，dp[i-1][x] 是上一次循环保存下来的值；
因此，可以将 dp 缩成一维数组 dp[C+1]，从而达到优化空间的目的，状态转移方程转换为：
dp[j] = max(dp[j], dp[j-w[i]] + v[i])。
注意：之前是二维数组，dp[i][j] 的更新依赖于 dp[i-1][x] 的结果。但是变成了一维数组后，对于一件物品 i，如果内层循环 j 仍然从小到大遍历，刚刚更新的值在往后遍历时又会被重新覆盖，导致错误的答案。
举例（如果内存循环从小到大遍历）：
物品 1 的更新，没有问题：
物品 2 的更新，出错：
解决这种覆盖问题的方法就是：内存循环从大到小遍历，这样就不会出现覆盖值的情况。这样的话，物品 i 的所有更新就是依赖于 i-1 轮的结果，而不像从 j 小到大遍历那样对当前更新的结果可能又重新覆盖。
因此对于物品 2，就能得到下面的正确更新结果：
同时，因为内层循环 j 从大到小遍历了，所以只需要从容量 C 遍历到 w[i-1] 即可。因为对于 j < w[i-1]，一维数组 dp 中已经有了，即就是二维数组下 dp[i-1][j] 的结果。所以对于 j < w[i-1] 的情况，不用更新即可。
空间优化的代码如下：
dp = [0] * (C+1)
for i in range(1, N+1):
for j in range(C, w[i-1]-1, -1): # j 从 C 开始从大到小递减到 w[i-1]
dp[j] = max(dp[j], dp[j-w[i-1]] + v[i-1])
return dp[-1]
这样，时间复杂度虽然还是 O(n^2)，但是空间复杂度从 O(n^2) 变成了 O(n)。
1.5、与01-背包相关的Leetcode题目：
【2】完全背包及其应用
2.1、完全背包问题描述：
有 N 种物品和一个容量是 C 的背包，每种物品都有无限件可用。第 i 种物品的重量是 wi，价值是 vi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
如01-背包中的例子，最大价值是 12，即可以在容量为 8 的背包中装入 4 件物品 1，总价值 4 * 3 = 12。
2.2、完全背包解题思路：
与01-背包不同的是，完全背包问题是指每种物品都有无限个。但是，完全背包问题的解答几乎与01-背包的一维数组解答一模一样，唯一的区别是内层循环 j 的遍历次序是递增的，即 j 从 w[i-1] 到 C。
为什么？
- 在01-背包中，dp 依赖的是 i-1 轮的结果。但是完全背包问题中，dp 依赖的未必是 i-1 轮的状态，而是同一轮中较小的 j。比如 C = 8，重量为 2 的物品在一轮更新时可以装很多次。
- 01-背包中，要验证当前第 i 个物品是否拿还是不拿必须依赖 i-1轮的状态，绝对不会出现已经拿取了第 i 个物品的情况。但是在完全背包中，由于物品有多个，可能要验证当前是否已经取过若干个第 i 个物品了。
- 所以内层循环 j 的遍历是由小到大递增的。
其实很简单地可以理解为：有一个一维数组 dp[C+1]，对于每件物品，尽可能多的装进去，不断地用最大价值去刷新这个数组。最后，得到的 dp[-1] 就是最后的答案。
2.3、Python3 实现：
class Solution:
def knapsack01(self, N, w, v, C):
'''
@param N: int, 物品总数
@param w: List, 物品重量
@param v: List, 物品价值
@param C: int, 背包容量
'''
dp = [0] * (C+1)
for i in range(1, N+1):
for j in range(w[i-1], C+1): # j 从 w[i-1] 开始从小到大递增到 C
dp[j] = max(dp[j], dp[j-w[i-1]] + v[i-1])
return dp[-1]
N = 4
w = [2,3,4,5]
v = [3,4,5,6]
C = 8
print(Solution().knapsack01(N, w, v, C)) # 12
2.4、与完全背包相关的Leetcode题目：
【3】多重背包
多重背包问题限定了一种物品的个数。解决多重背包问题，只需要把它转化为01-背包问题即可。
比如，有 2 件价值为 5，重量为 2 的同一物品，我们就可以分为物品 a 和物品 b，a 和 b 的价值都为 5，重量都为 2，但我们把它们视作不同的物品。
之后，做法与01-背包相同。代码参考01-背包代码即可。
网友评论