背包问题知识（一）

1. 背包问题简介

1.1 背包问题的定义

背包问题：背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 $W$ 的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？

根据物品限制条件的不同，背包问题可分为：0-1 背包问题、完全背包问题、多重背包问题、分组背包问题，以及混合背包问题等。

1.2 背包问题的暴力解题思路

背包问题的暴力解题思路比较简单。假设有 $n$ 件物品。我们先枚举出这 $n$ 件物品所有可能的组合。然后再判断这些组合中的物品是否能放入背包，以及是否能得到最大价值。这种做法的时间复杂度是 $O(2^n)$。

背包问题暴力解法的时间复杂度是指数级别的，我们可以利用动态规划算法减少一下时间复杂度。

下面我们来讲解一下如何使用动态规划方法解决各种类型的背包问题。

2. 0-1 背包问题

0-1 背包问题：有 $n$ 件物品和有一个最多能装重量为 $W$ 的背包。第 $i$ 件物品的重量为 $weight[i]$，价值为 $value[i]$，每件物品有且只有 $1$ 件。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

2.1 0-1 背包问题基本思路

0-1 背包问题的特点：每种物品有且仅有 $1$ 件，可以选择不放入背包，也可以选择放入背包。

思路 1：动态规划 + 二维基本思路

1. 划分阶段

按照物品的序号、当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 $dp[i][w]$ 表示为：前 $i$ 件物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。

状态 $dp[i][w]$ 是一个二维数组，其中第一维代表「当前正在考虑的物品」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。

3. 状态转移方程

对于「将前 $i$ 件物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值 」这个子问题，如果我们只考虑第 $i - 1$ 件物品（前 $i$ 件物品中最后一件物品）的放入策略（放入背包和不放入背包两种策略）。则问题可以转换为一个只跟前 $i - 1$ 件物品相关的问题。

1. 第 $i - 1$ 件物品不放入背包：问题转换为「前 $i - 1$ 件物品放入一个最多能装重量为 $w$ 的背包中 ，可以获得的最大价值」为 $dp[i - 1][w]$。
2. 第 $i - 1$ 件物品放入背包：问题转换为「前 $i - 1$ 件物品放入一个最多能装重量为 $w - weight[i - 1]$ 的背包中，可以获得的最大价值」为 $dp[i - 1][w - weight[i - 1]]$，再加上「放入的第 $i - 1$ 件物品的价值」为 $value[i - 1]$，则此时可以获得的最大价值为 $dp[i - 1][w - weight[i - 1]] + value[i - 1]$。

接下来我们再来考虑一下第 $i - 1$ 件物品满足什么条件时才能考虑是否放入背包，并且在什么条件下一定不能放入背包。

1. 如果当前背包的载重不足时（即 $w < weight[i - 1]$）：第 $i - 1$ 件物品一定不能放入背包，此时背包的价值 $dp[i][w]$ 仍为 $dp[i - 1][w]$ 时的价值，即 $dp[i][w] = dp[i - 1][w]$。
2. 如果当前背包的载重足够时（即 $w \ge weight[i - 1]$）：第 $i - 1$ 件物品可以考虑放入背包，或者不放入背包，此时背包的价值取两种情况下的最大值，即 $dp[i][w] = max \lbrace dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1] \rbrace$。

则状态转移方程为：

$dp[i][w] = \begin{cases} dp[i - 1][w] & w < weight[i - 1] \cr max \lbrace dp[i - 1][w], \quad dp[i - 1][w - weight[i - 1]] + value[i - 1] \rbrace & w \ge weight[i - 1] \end{cases}$

4. 初始条件

• 如果背包载重上限为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[i][0] = 0, 0 \le i \le size$。
• 无论背包载重上限是多少，前 $0$ 件物品所能获得的最大价值一定为 $0$，即 $dp[0][w] = 0, 0 \le w \le W$。

5. 最终结果

根据我们之前定义的状态，$dp[i][w]$ 表示为：前 $i$ 件物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[size][W]$，其中 $size$ 为物品的件数，$W$ 为背包的载重上限。

思路 1：代码

class Solution:
    # 思路 1：动态规划 + 二维基本思路
    def zeroOnePackMethod1(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 第 i - 1 件物品装不下
                if w < weight[i - 1]:
                    # dp[i][w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」
                    dp[i][w] = dp[i - 1][w]
                else:
                    # dp[i][w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1])
                    
        return dp[size][W]

思路 1：复杂度分析

• 时间复杂度：$O(n \times W)$，其中 $n$ 为物品数量，$W$ 为背包的载重上限。
• 空间复杂度：$O(n \times W)$。

2.2 0-1 背包问题滚动数组优化

根据之前的求解过程可以看出：当我们依次处理前 $1 \sim n$ 件物品时，「前 $i$ 件物品的处理结果」只跟「前 $i - 1$ 件物品的处理结果」，而跟之前更早的处理结果没有太大关系。

也就是说在状态转移的过程中，我们只用到了当前行（第 $i$ 行）的 $dp[i][w]$ 以及上一行（第 $i - 1$ 行）的 $dp[i - 1][w]$、$dp[i - 1][w - weight[i - 1]]$。

所以我们没必要保存所有阶段的状态，只需要保存上一阶段的所有状态和当前阶段的所有状态就可以了，这样使用两个一维数组分别保存相邻两个阶段的所有状态就可以实现了。即：用 $dp[0][w]$ 保存原先 $dp[i - 1][w]$ 的状态，用 $dp[1][w]$ 保存当前 $dp[i][w]$ 的状态。

其实我们还可以进一步进行优化，我们只需要使用一个一维数组 $dp[w]$ 保存上一阶段的所有状态，采用使用「滚动数组」的方式对空间进行优化（去掉动态规划状态的第一维）。

思路 2：动态规划 + 滚动数组优化

1. 划分阶段

按照当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。

3. 状态转移方程

$dp[w] = \begin{cases} dp[w] & w < weight[i - 1] \cr max \lbrace dp[w], dp[w - weight[i - 1]] + value[i - 1] \rbrace & w \ge weight[i - 1] \end{cases}$

在第 $i$ 轮计算之前，$dp[w]$ 中保存的是「第 $i - 1$ 阶段的所有状态值」。在第 $i$ 轮计算之后，$d[w]$ 中保存的是「第 $i$ 阶段的所有状态值」。

为了保证第 $i$ 轮计算过程中，$dp[w]$ 是由第 $i - 1$ 轮中 $dp[w]$ 和 $dp[w - weight[i - 1]]$ 两个状态递推而来的值，我们需要按照「从 $W \sim 0$ 逆序的方式」倒推 $dp[w]$。

这是因为如果我们采用「从 $0 \sim W$ 正序递推的方式」递推 $dp[w]$，如果当前状态 $dp[w - weight[i]]$ 已经更新为当前第 $i$ 阶段的状态值。那么在向右遍历到 $dp[w]$ 时，我们需要的是第 $i - 1$ 阶段的状态值（即上一阶段的 $dp[w - weight[i - 1]]$），而此时 $dp[w - weight[i - 1]]$ 已经更新了，会破坏当前阶段的状态值，从而无法推出正确结果。

而如果按照「从 $W \sim 0$ 逆序的方式」倒推 $dp[w]$ 则不会出现该问题。

因为 $w < weight[i - 1]$ 时，$dp[w]$ 只能取上一阶段的 $dp[w]$，其值相当于没有变化，这部分可以不做处理。所以我们在逆序倒推 $dp[w]$ 时，只需遍历到 $weight[i - 1]$ 时即可。

4. 初始条件

• 无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 $0$，即 $dp[w] = 0, 0 \le w \le W$。

5. 最终结果

根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[W]$，其中 $W$ 为背包的载重上限。

思路 2：代码

class Solution:
    # 思路 2：动态规划 + 滚动数组优化
    def zeroOnePackMethod2(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
                
        return dp[W]

思路 2：复杂度分析

• 时间复杂度：$O(n \times W)$，其中 $n$ 为物品数量，$W$ 为背包的载重上限。
• 空间复杂度：$O(W)$。

2.3 0-1 背包问题的应用

2.3.1 题目链接

• 416. 分割等和子集 - 力扣

2.3.2 题目大意

描述：给定一个只包含正整数的非空数组 $nums$。

要求：判断是否可以将这个数组分成两个子集，使得两个子集的元素和相等。

说明：

• $1 \le nums.length \le 200$。
• $1 \le nums[i] \le 100$。

示例：

• 示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]。

• 示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

2.3.3 解题思路

思路 1：动态规划

这道题换一种说法就是：从数组中选择一些元素组成一个子集，使子集的元素和恰好等于整个数组元素和的一半。

这样的话，这道题就可以转变为「0-1 背包问题」。

1. 把整个数组中的元素和记为 $sum$，把元素和的一半 $target = \frac{sum}{2}$ 看做是「0-1 背包问题」中的背包容量。
2. 把数组中的元素 $nums[i]$ 看做是「0-1 背包问题」中的物品。
3. 第 $i$ 件物品的重量为 $nums[i]$，价值也为 $nums[i]$。
4. 因为物品的重量和价值相等，如果能装满载重上限为 $target$ 的背包，那么得到的最大价值也应该是 $target$。

这样问题就转变为：给定一个数组 $nums$ 代表物品，数组元素和的一半 $target = \frac{sum}{2}$ 代表背包的载重上限。其中第 $i$ 件物品的重量为 $nums[i]$，价值为 $nums[i]$，每件物品有且只有 $1$ 件。请问在总重量不超过背包载重上限的情况下，能否将背包装满从而得到最大价值？

1. 划分阶段

按照当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 $dp[w]$ 表示为：从数组 $nums$ 中选择一些元素，放入最多能装元素和为 $w$ 的背包中，得到的元素和最大为多少。

3. 状态转移方程

$dp[w] = \begin{cases} dp[w] & w < nums[i - 1] \cr max \lbrace dp[w], \quad dp[w - nums[i - 1]] + nums[i - 1] \rbrace & w \ge nums[i - 1] \end{cases}$

4. 初始条件

• 无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 $0$，即 $dp[w] = 0, 0 \le w \le W$。

5. 最终结果

根据我们之前定义的状态，$dp[target]$ 表示为：从数组 $nums$ 中选择一些元素，放入最多能装元素和为 $target = \frac{sum}{2}$ 的背包中，得到的元素和最大值。

所以最后判断一下 $dp[target]$ 是否等于 $target$。如果 $dp[target] == target$，则说明集合中的子集刚好能够凑成总和 $target$，此时返回 True；否则返回 False。

思路 1：代码

class Solution:
    # 思路 2：动态规划 + 滚动数组优化
    def zeroOnePackMethod2(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
                
        return dp[W]

    def canPartition(self, nums: List[int]) -> bool:
        sum_nums = sum(nums)
        if sum_nums & 1:
            return False

        target = sum_nums // 2
        return self.zeroOnePackMethod2(nums, nums, target) == target

思路 1：复杂度分析

• 时间复杂度：$O(n \times target)$，其中 $n$ 为数组 $nums$ 的元素个数，$target$ 是整个数组元素和的一半。
• 空间复杂度：$O(target)$。

参考资料

• 【资料】背包九讲 - 崔添翼
• 【文章】背包 DP - OI Wiki
• 【文章】背包问题 第四讲 - 宫水三叶的刷题日记
• 【文章】Massive Algorithms: 讲透完全背包算法