01-背包、完全背包、多重背包及其相关应用

2019-06-05  本文已影响0人  牛奶芝麻

本文介绍了背包问题系列，主要包括：

【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]，那么分为两种情况：

如上述例子，从上到下填表如下（第一行和第一列为边界条件初始化）：

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题目：

【416】判断一个数组是否可以划分成两个相等的子集和

【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。

为什么？

其实很简单地可以理解为：有一个一维数组 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题目：

【322】找硬币问题，求需要的最少硬币数

【3】多重背包

多重背包问题限定了一种物品的个数。解决多重背包问题，只需要把它转化为01-背包问题即可。

比如，有 2 件价值为 5，重量为 2 的同一物品，我们就可以分为物品 a 和物品 b，a 和 b 的价值都为 5，重量都为 2，但我们把它们视作不同的物品。

之后，做法与01-背包相同。代码参考01-背包代码即可。

上一篇下一篇

猜你喜欢

热点阅读