背包问题大全解

0-1背包

• 二维数组解法
建一个二维数组 dp，dp[i][j] 表示从下标为 [0 - i] 的物品中任意选取，装入容量为 j 的背包，所能获得的最大价值。



对数组进行初始化。

dp = [[0] * (capacity + 1) for _ in range(weight)]
for i in range(weight[0], capacity + 1):
	dp[0][i] = weight[0]

当 j = 0 时，背包装不下任何东西，所能得到的价值为 0. 因此对于任意 i， dp[i][0] = 0. 当只有一件物品可选时，能装入的价值要么等于该物品价值，要么等于 0（该物品装不下）。据此，我们可以初始化 dp[0]。初始化后的 dp 数组如上图。
接下来进行推演，以得到状态转移方程。
dp[i] 相对于 dp[i - 1] 来说，区别在于多了物品 i 可供选择。那么根据物品 i 的重量，dp[i][j] 的值有两种情况：
• weight[i] > j
即物品 i 无法装入背包，因此多了这个物品并没有什么分别。
dp[i][j] = dp[i - 1][j]
• weight[i] ≤ j
物品 i 可以装入背包，我们应该尝试这个新物品能否给我们带来更大的价值。将背包腾空一些，正好能够放下该物品就行，然后放入该物品计算一下总价值（dp[i - 1][j - weight[i]] + value[i]），看是不是比不放此物品的价值（dp[i - 1][j]）大。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i] + value[i])
有了初始值，有了状态转移方程，就可以开始推演结果了。

for i in range(1, len(weight)):
	for j in range(1, capacity + 1):
		dp[i][j] = dp[i - 1][j] if weight[i] > j else max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

返回数组的最后一个元素，即是本题的结果。
代码中的两个循环遍历，我们先遍历了物品，后遍历了背包容量，这很符合直觉。能否颠倒一下，先遍历背包容量，后遍历物品呢？
作为一个纯0-1背包问题的二维数组解法，是可以颠倒的。（其他非「纯0-1背包问题」，非一维数组解法，后面再探讨。）

for j in range(1, capacity + 1):
	for i in range(1, len(weight)):
		dp[i][j] = dp[i - 1][j] if weight[i] > j else max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

可颠倒的原因在于，dp[i][j] 的计算，依赖于一维下标为 i-1 ，二维下标为 j 或 j - weight[i] 的元素。从几何位置上来看，其依赖的是其左上方的元素。而无论我们是先遍历一维还是先遍历二维，都能够保证左上方的元素先于当前元素访问。

---

💡
再来琢磨一个问题，我们的动态规划，背包容量是从 0 开始的，可选物品是从数量为 1 开始的。我们为什么没有从可选物品数量为 0 开始呢？能否这样做呢？答案是完全可以。



并且，多了这一行后，我们发现，只有一个物品时的数据也可以根据第 0 行推演出来，推演公式是一模一样的。这样，我们的初始化就更简单了。
那么一开始为什么没有这样做呢，主要还是为了便于理解。在我们这个新的数组里，dp[i][j] 表示的背包容量仍是 j，但是其所可选取的范围是 0 ~ i-1，琢磨的也是第 i-1 个物品要不要放入的问题，关心的是 weight[i - 1] 和 value[i -1]，为了让大家少转一个弯，所以还是采用了见 i 是 i 的方式。
在这个新的 dp 数组下，代码是这样的：

dp = [[0] * (capacity + 1) for _ in range(len(weight) + 1)]
for i in range(1, len(weight) + 1):
	for j in range(1, capacity + 1):
		dp[i][j] = dp[i - 1][j] if weight[i - 1] > j else max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])

代码上的区别就在于初始化更简单了，以及 weight[i - 1]、value[i - 1] 的下标变化。

• 一维数组解法
观察二维解法我们会发现，第 i 行数据的计算，仅依赖于第 i-1 行。那么我们完全不用保存整张二维数组的所有数据，仅用一个数组即可完成计算。

dp = [0] * (capacity + 1)
for i in range(weight[0], capacity + 1):
	dp[i] = value[0]

for i in range(1, len(weight)):
    for j in range(capacity, weight[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

注意在内循环中，背包容量是从后往前遍历的。这很好理解，在二维数组中，第 i 行依赖于第 i-1 行，体现在一维数组中则是新数据依赖于旧数据。而数组右侧的数据又依赖于左侧的数据。要保证这两个依赖不被破坏，我们只能从后往前遍历。
那么，一维数组解法，两个循环是否能颠倒呢？
就此题此解来说（纯0-1背包的一维数组解法），答案显然是不能。我们之所以能够把二维降为一维，就是因为利用了数据更新上的时间差。也就是第 i 层和第 i-1 层之间，从右往左依赖的时间差。所以我们从右往左遍历的时候，右边元素的更新，依赖的是左边的元素，转换到二维数组里，其实是第 i-1 层左边的元素。即我们的这个一维数组，已经更新的（右边的元素）是第 i 层的元素，尚未更新的（左边的元素）是第 i-1 层的元素。因此，内循环从右往左，外循环从 i-1 到 i，这是无法改变的。

---

💡
同样引申之前所说的从可选物品数量为 0 为起始。我们发现在一维数组中实现起来甚至更顺。

dp = [0] * (capacity + 1)
for i in range(1, len(weight) + 1):
	for j in range(capacity, weight[i - 1] - 1, -1):
		dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1])

这个从可选物品数量为 0 开始的思考方式非常关键，从本质上来说，它才是咱们推理的源头。只不是为了便于理解，咱们多做一步，把 1 个物品的情况手动推理了，也可以。所以咱们下面还是按从 1 个物品开始推理来讲解。（也不排除存在无法从 0 状态推理到 1 状态的情况，这个我不打包票，但是我还没遇见过。）

完全背包

• 二维数组解法
状态转移方程：
• weight[i] > j
即物品 i 无法装入背包，因此多了这个物品并没有什么分别。
dp[i][j] = dp[i - 1][j]
• weight[i] ≤ j
物品 i 可以装入背包，我们应该尝试装入该物品，与不装该物品比较，看是否得到更大价值。
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i] + value[i])
数据初始化也与 0-1 背包有所区别。



dp = [[0] * (capacity + 1) for _ in range(len(weight))]
for i in range(weight[0], capacity + 1):
	dp[0][i] = dp[0][i - weight[0]] + value[0]

通过遍历推演结果。

for i in range(1, len(weight)):
	for j in range(1, capacity + 1):
		dp[i][j] = dp[i - 1][j] if weight[i] > j else max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

接下来探讨循环是否可颠倒。（为什么我们老在乎能不能颠倒的问题呢，直接按照最符合直觉的方法来写，保证不会出错不就好了？不然，在背包问题的某些问题中，循环的嵌套顺序恰恰就是解题的关键，我们从一开始的纯背包问题就关注循环嵌套顺序、遍历方向，对我们后面的理解是十分有帮助的。）
答案是可以（纯完全背包，二维数组解法）。究其原因，跟之前的分析是一样的。当前元素的计算，只依赖于其左边，其上边的元素。只要能够保证这个顺序，我们把循环颠倒一下也没关系。

for j in range(1, capacity + 1):
	for i in range(1, len(weight)):
		dp[i][j] = dp[i - 1][j] if weight[i] > j else max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

• 一维数组解法

dp = [0] * (capacity + 1)
for i in range(weight[0], capacity + 1):
	dp[i] = dp[i - weight[0]] + value[0]

for i in range(1, len(weight)):
	for j in range(weight[i], capacity + 1):
		dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

发现端倪！这里内循环又变成从左往右了！（0-1 背包一维数组解法内循环是从右往左的。）
究其本质，原因都是一致的。我们展开到二维来看，dp[i][j] 依赖于 dp[i][j - weight[i]]，前面说过了，二维数组中的 dp[i] 和 dp[i - 1] 反映到一维数组中，就是一种时序上的区别，在第 i 轮循环中，dp[i - 1] 就是更新之前的数据，dp[i] 就是更新之后的数据。此时，我们依赖于更新后的数据，右边又依赖左边，所以当然就要从左往右更新了。
再次，此场景（纯完全背包，一维数组解法）的循环能颠倒吗？不行，我们要保持从 i-1 到 i 的渐进关系不被打破，此处一维数组的循环仍然不能颠倒。
 

多重背包

• 二维数组解法

# 初始化
dp = [[0] * (capacity + 1) for _ in range(len(weight))]
for i in range(weight[0], capacity + 1):
    k = 1
    while k <= nums[0] and i - k * weight[0] >= 0:
        dp[0][i] = max(dp[0][i], 0 + k * value[0])
        k += 1

# 推演
for i in range(1, len(weight)):
	for j in range(1, capacity + 1):
		dp[i][j] = dp[i - 1][j]
		k = 1
		while k <= nums[i] and j - k * weight[i] >= 0:
			dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weight[i]] + k * value[i])
			k += 1

逻辑也很简单：装 1 件试试、装 2 件试试、装 3 件试试。。
但是呢，我们看代码中 dp 数组的初始化，不免就琢磨过味来了。这个初始化，略显复杂啊。
再想想我们前面所说的以没有物品作为初始条件，是否会更简单呢？确实如此。

dp = [[0] * (capacity + 1) for _ in range(len(weight) + 1)]

for i in range(1, len(weight) + 1):
    for j in range(1, capacity + 1):
        dp[i][j] = dp[i - 1][j]
        k = 1
        while k <= nums[i - 1] and j - k * weight[i - 1] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weight[i - 1]] + k * value[i -1])
            k += 1

循环的嵌套顺序（多重背包，二维数组解法）也是颠倒的，就不上代码了。

• 一维数组解法
我们直接上以无物品作为起始条件的代码。

dp = [0] * (capacity + 1)

for i in range(1, len(weight) + 1):
    for j in range(capacity, 0, -1):
        k = 1
        while k <= nums[i - 1] and j - k * weight[i - 1] >= 0:
            dp[j] = max(dp[j], dp[j - k * weight[i - 1]] + k * value[i - 1])
            k += 1

组合问题

无顺序组合

• 二维数组解法

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        if amount == 0:
            return 1
        elif not coins:
            return 0

        dp = [[0] * (amount + 1) for _ in range(len(coins))]
        for row in dp:
            row[0] = 1

        for i in range(len(coins)):
            for j in range(1, amount + 1):
                dp[i][j] = dp[i - 1][j] if coins[i] > j else dp[i - 1][j] + dp[i][j - coins[i]]
        return dp[-1][-1]

dp[i][j] 表示从下标为 0-i 的金币中任意挑选，使总金额为 j 的组合数。
这其实跟纯 0-1 问题没有多大差别，只是 max() 换成了 + 罢了。
此场景下，内外循环也是可以颠倒的，就不贴代码了。

• 一维数组解法

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        if amount == 0:
            return 1
        elif not coins:
            return 0

        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] += dp[x - coin]
        return dp[-1]

也就是纯 0-1 背包问题的一维解法递推过来。
那么这个场景下，内外循环能否颠倒呢，答案显然也是不能，原因跟纯 0-1 背包的一维解法不能颠倒是一样的。

有顺序组合

• 二维数组解法

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if target == 0:
            return 1
        if not nums:
            return 0
        
        dp = [[0] * (target + 1) for _ in range(len(nums))]
        for row in dp:
            row[0] = 1
        
        for j in range(1, target + 1):
            for i in range(len(nums)):
                dp[i][j] = dp[i - 1][j] if nums[i] > j else dp[i - 1][j] + dp[-1][j - nums[i]]
        return dp[-1][-1]

比较一下无顺序问题中的二维解法，关键区别在于：

# 无顺序组合
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - coins[i]]
# 有顺序组合
dp[i][j] = dp[i - 1][j] + dp[-1][j - nums[i]]

体现在二维数组中的差异如下：



图中，蓝色的 dp[i][j] 由黄色的两个元素相加所得。该如何来解读二者的含义呢？
对于不区分顺序的组合来说，我们可以把数组 coins 的顺序给锁死，遍历的时候只需要管前面已经遍历过的元素，不用管尚未遍历到的元素，反正后面的元素也过不了前面来。前面的元素先被挑选，后面的元素后被挑选。
但是当新的顺序就是一个新的组合的时候，我们不能将 nums 这个数组的元素顺序锁死。当我们要计算 dp[i][j] 时，如果只把眼光放在 dp[i - 1] 上，那岂不是把「后面的元素先被选用」这种情况完全忽略了吗？实际上，在后面的元素也有需要被先选的情况下，i 已经不能约束元素的先后顺序了，那么 dp[i][j] 的含义是什么呢，我们应该如何理解 i 在其中的意义呢？
控制变量法，我们固定 j 不动，看在不同的 i 中，dp[i][j] 所表达的意义。大家知道，最终我们关心的只是最后一行，但是这最后一行的结果，又是由前面的行逐步累加过来的，琢磨出点味儿了，迭代，有点迭代的味道。i 是对 nums 数组进行遍历的一个迭代因子。再把它具象化一点，我们计算的是组合的种类，不妨把可能的组合分个类，就按尾元素来分好了（就像我们交作业的时候，按学号尾数来交一样），我们的 i 从 0 迭代到 len(nums - 1)，也就是把所有可能的组合，按尾元素从 nums[0] 到 nums[-1] 分了个类，绝不重复。
那么，以 nums[i] 为尾的组合有多少种呢？尾元素是固定的，自然是前面的组合有多少种，那就有多少种。加上尾元素的和是 j，去掉尾元素，那不就是 j - nums[i] 嘛，组合总数，那不就是 dp[-1][j - nums[i]] 吗？
现在再来看一看转移方程：dp[i][j] = dp[i - 1][j] + dp[-1][j - nums[i]]
这不就是以 nums[i] 为尾元素的组合数（dp[-1][j - nums[i]]），再累加上前面已经计算的总数（dp[i - 1][j]）吗？
怎么样，是不是有一种通透感。其实这个场景，我们用一维数组的解法，会「看起来」更顺畅一点，因为在一维数组解法中，这个 i 就真的是一个纯粹的迭代。但是，「看起来」的顺畅，会使你心中的疑惑被巧妙地粉饰和掩藏。真正把它摊开后，你发现自己心中还是有疙瘩没有捋顺。这也就是我们一直如此坚持，如此愚笨地，非得二维解法、一维解法一个不落，一遍遍讲的原因了。

• 一维数组解法

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1,target+1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[target]

对于此场景（有顺序组合，一维解法）的解法，我们就再钻进去唠叨了。就追问一个问题：循环能颠倒吗？
不能。nums 的遍历就是一个迭代，我们在一轮迭代中计算完了和为 j - 1 的组合数，再在一轮新的迭代中计算和为 j 的组合数。因而，nums 的遍历，一定是内循环。

True / False 问题

• 二维数组解法

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if not nums or len(nums) <= 1:
            return False
        if sum(nums) % 2 == 1:
            return False

        target = sum(nums) // 2        
        dp = [[False] * (target + 1) for _ in range(len(nums))]
        for row in dp:
            row[0] = False
        if nums[0] <= target: dp[0][nums[0]] = True

        for i in range(1, len(nums)):
            for j in range(1, target + 1):
                dp[i][j] = (dp[i - 1][j] or dp[i - 1][j - nums[i]]) if j >= nums[i] else dp[i - 1][j]
        return dp[-1][-1]

内外循环能颠倒吗？可以的，与之前的分析一致。

• 一维数组解法

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if not nums or len(nums) <= 1:
            return False
        if sum(nums) % 2 == 1:
            return False
        target = sum(nums) // 2
        
        dp = [False] * (target + 1)
        if nums[0] <= target: dp[nums[0]] = True

        for i in range(1, len(nums)):
            for j in range(target, nums[i] - 1, -1):
                dp[j] = dp[j] or dp[j - nums[i]]
        return dp[-1]

内外循环能颠倒吗？不行的，与之前的分析一致。

问题整理

• 最大最小问题
322. Coin Change

• 组合问题
518. Coin Change 2 （无顺序组合）
377. Combination Sum IV （有顺序组合）

• True / False 问题
416. Partition Equal Subset Sum

题外絮叨

• 分数背包问题
分数背包问题的题干和 0-1 类似，区别在于物品可以部分装入，而不是只能做出二元（0-1）选择。但是这道题我认为不应该放到背包问题这个大类里面来讲，因为背包问题的特点和难点就在于物品重量和物品价值的取舍。而如果商品可以部分装入，这个制约关系也就不存在了，物品的最优选择变得非常容易。
在《算法导论》中，分数背包问题是用来和 0-1 背包问题做对比，以比较贪心算法和动态规划的区别。在分数背包问题中，我们只需要计算物品的单位价值 v/w, 然后优先选择单位价值高的物品就可以了。这是因为物品可以部分装入，所以我们可以保证要么背包被装满，要么物品被装完。而 0-1 背包问题则无法用贪心算法解决。

参考资料

力扣

https://leetcode-cn.com/circle/article/lUki6J/

力扣

https://leetcode-cn.com/circle/article/k7RRg3/

力扣

https://leetcode-cn.com/circle/article/2ZcRi7/

力扣

https://leetcode-cn.com/problems/combination-sum-iv/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-wen-/