01背包理论基础

理论基础

题目描述

有 n 件物品和一个最多能背重量为w 的背包，已知第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里，可以使得物品价值总和最大。

暴力解法

本题太过于经典，以至于第一反应肯定都是动态规划。本题中，每个物品的状态就是“选”或“不选”，回溯算法可以很好地解决这样的组合问题。假设本题中的物品有 n 个，则叶子节点一共应该有 $2^n$ 个。毫无疑问，指数级别的复杂度肯定会超时。

动态规划

dp 数组下标的含义：
- dp[i][j]：给定下标为 [0, i] 的物品和重量为 j 的背包，能够获得的最大物品价值总和
dp 递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
- 给定了下标为 [0, i] 的物品，可以向前推一步
- 如果不选择物品 i 能够获得更多的价值，则 dp[i][j] = dp[i-1][j]
  - 因为此时物品 i 没有被选择，可用的背包空间没有变化
- 如果选择物品 i 能够获得更多的价值，则 dp[i][j] = dp[i-1][j - weight[i]] + value[i]
  - 因为此时物品 i 被选择了，可用的背包空间变少了，同时得到了物品 i 的价值
- 由于不知道每一次状态转移时，应不应该选择当前物品，所以对这两种情况取一个最大值
dp 数组的初始化：
- 要明确二维 dp 数组的格式：对于每一个可能的背包重量都应该列举。例如，
  
  物品重量价值
  物品 0 1 15
  物品 1 3 10
  物品 2 4 30
  
  此时只有三个物品，但所需要的重量应该是 [0, w] 中所有的非负整数（w 为给定的最大重量）。
- 对于 dp[i][0]，既然背包的最大重量是 0，什么都不能装，所以能获得的最大价值为 0
- 对于 dp[0][j]，当背包允许的重量 j >= weight[0] 时，能获得的最大价值就是 value[0]，否则最大价值也为 0
- 其余的值没有特定要求，因为 dp 的状态转移会直接赋值
遍历顺序：使用二维数组时，很显然有两个维度（物品价值和物品重量）
- 根据 dp 的状态转移公式可知，(i, j) 计算需要左上角的矩形区域都先完成计算
- 因此，先遍历价值和先遍历重量都能够解决本题
- 注意，如果当前物品的重量超过了当前允许的背包承重 j，则直接进行状态转移 dp[i][j] = dp[i-1][j]，否则会报错
举例推导 dp 数组：

物品	重量	价值
物品 0	1	15
物品 1	3	10
物品 2	4	30

def test_2_wei_bag_problem1(weight, value, bagweight):# 二维数组dp = [[0] * (bagweight + 1) for _ in range(len(weight))]# 初始化for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]# weight数组的大小就是物品个数for i in range(1, len(weight)):  # 遍历物品for j in range(bagweight + 1):  # 遍历背包容量if j < weight[i]:dp[i][j] = dp[i - 1][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])return dp[len(weight) - 1][bagweight]if __name__ == "__main__":weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4result = test_2_wei_bag_problem1(weight, value, bagweight)print(result)

01背包 (滚动数组)

理论基础

在二维数组中，dp 公式为 dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])，我们认为当前 dp[i, j] 依赖于左上角的那个矩形区域。实际上，dp[i, j] 仅仅依赖于上一层的左侧。如下图，绿色区域的值只取决于黄色区域。

这样对上一层的依赖决定了我们其实没有必要保存整个矩阵，只需要保存一个一维数组即可。

dp 数组下标的含义：
- dp[j]：给定重量为 j 的背包，能够获得的最大物品价值总和
dp 递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，还是有两个选择
- 选择放入当前的物品 i，得到 dp[j - weight[i]] + value[i]
- 不选择放入当前物品 i，维持之前的 dp[j]
- 相比于之前的二维 dp 公式同时省略了 [i-1]，这也意味着在进行递推的时候，所使用的值都是没有经历过物品 i 的更新的（也就是上一层考虑过物品 i-1 之后的值）
dp 数组的初始化：
- 毫无疑问，dp[0] = 0。其余的值会在第一次更新之后被改写。由于涉及到了对当前值的比较中取 max，所以初始化的值不能影响 max 的结果，考虑到题目中的值都是正整数，初始化均为 0 即可。
遍历顺序：滚动数组的重点！
```
	for i in range(len(weight)):  # 遍历物品for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
```
- 在遍历背包容量（对应二维数组的层遍历）时，是从后往前遍历的，这和二维数组很不一样。因为进行递推的时候，所使用的值都是没有经历过物品 i 的更新的，所以不能在针对当前物品 i 更新 dp[j]之前改变当前的 dp[k], k <= j 的值，只能后序遍历。
  - 如果进行前序遍历，只会试图重复加入物品（直接举例即可证明）
  - 而在二维数组解法中，并没有覆盖过上一层物品 i 的结果，所以无需采用倒叙遍历
- 遍历顺序必须是先物品后容量。由于维持了一维数组，如果遍历顺序颠倒，dp[j] 就能记录背包容量为 j 时能够获得的一件物品的最大价值，因为初始值总是固定的。
举例推导 dp 数组：

def test_1_wei_bag_problem(weight, value, bagWeight):# 初始化dp = [0] * (bagWeight + 1)for i in range(len(weight)):  # 遍历物品for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])return dp[bagWeight]if __name__ == "__main__":weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4result = test_1_wei_bag_problem(weight, value, bagweight)print(result)

01背包总结

以上总结了两种01背包的解法：二维数组在清楚定义的情况下，更为简单明了，收到的限制也更少，但空间复杂度较高；一维滚动数组思路巧妙，需要特定的遍历顺序（内外层、倒序），但有超低的空间复杂度，代码简洁。

其中的难点（思维点）在于

不同维度的遍历顺序
同一纬度的前后遍历顺序
不同的递推公式
初始化逻辑

只有明白不同方法中以上难点的回答，才能真正理解01背包！

416. 分割等和子集

题目链接 | 理论基础

本题乍一看是典型的组合题：选取当前集合的子集，满足特定条件（和为一半）即可。经典的组合题自然应该想到回溯，然而回溯是暴力搜索（N叉树），拥有至少指数级的复杂度。当看到本题的数组长度，就该意识到回溯必然会超时。

从选取元素的角度看，每个元素最多只能使用一次，除了组合问题，也很符合01背包的设定。进行抽象后可以得到如下条件：

背包的总重量为 sum(nums) // 2
物品 i 的价值和重量均为 nums[i]
背包需要正好装满
每个物品 i 只能使用一次

二维 dp

dp 数组下标的含义：dp[i][j] 的含义是，给定元素 nums[:i+1]，背包容量为 j 时，能否正好装满当前背包
- dp[i][j] 是 boolean
dp 递推公式：dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
- 如果不选择当前元素 i，使用 nums[:i] 可以正好填满重量为 j 的背包，即是 dp[i-1][j]
- 如果选择当前元素，使用 nums[:i] 可以正好填满重量为 j - nums[i] 的背包，即是 dp[i-1][j-nums[i]]
- 这两种情况中，任意一种成立，则可以使用元素 nums[:i+1] 填满容量为 j 的背包；否则不可能
dp 数组的初始化：在执行 dp 之前，先将 nums 进行了从小到大的排序
- 为了不影响 or 的结果，所有值都先初始化为 False
- 对于元素 nums[0]，dp[0][nums[0]] = True
- 对于重量 j=0 的背包，任何情况都能装满，所以 dp[i][0] = 0（这对之后取一个元素的情况很重要）
dp 的遍历顺序：由于是二维数组，遍历顺序不那么重要，选择先遍历元素即可

举例推导：对于数组 [1, 5, 11, 5]，dp 数组如下

idx = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
dp = [[T, T, F, F, F, F, F, F, F, F, F, F],[T, T, F, F, F, T, T, F, F, F, F, F],[T, T, F, F, F, T, T, F, F, F, T, T],[T, T, F, F, F, T, T, F, F, F, T, T]]

class Solution:def canPartition(self, nums: List[int]) -> bool:nums.sort()         # sort in advance makes things easierif sum(nums) % 2:return Falsetarget_sum = sum(nums) // 2# dp[i][j] represents whether nums[:i+1] can exactly make the sum of jdp = [[False] * (target_sum + 1) for _ in range(len(nums))] # initialize the dp for nums[0]if nums[0] <= target_sum:dp[0][nums[0]] = True# initialize the dp for sum j=0for i in range(len(nums)):dp[i][0] = True# dp formulafor i in range(1, len(nums)):for j in range(target_sum + 1):if j < nums[i]:dp[i][j] = dp[i-1][j]else:dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]return dp[-1][-1]

一维 dp（滚动）

根据二维 dp 数组压缩成的滚动数组，注意遍历顺序要先物品后重量，同时重量的遍历要后序进行（由于对 nums 进行了排序，所以重量的遍历结束点可以直接确定）。

class Solution:def canPartition(self, nums: List[int]) -> bool:nums.sort()         # sort in advance makes things easierif sum(nums) % 2:return Falsetarget_sum = sum(nums) // 2# dp[i][j] represents whether nums[:i+1] can exactly make the sum of j# initialization to be False, so that it does not make effect when operating "or"dp = [False] * (target_sum + 1)# initialize the dp for sum j=0dp[0] = True# dp formulafor i in range(len(nums)):          # traverse nums from left to rightfor j in range(target_sum, nums[i]-1, -1):         # traverse sum j from right to leftdp[j] = dp[j] or dp[j - nums[i]]return dp[-1]

题解

以上我的思路（二维 dp 和滚动数组是同一种思路，不同的实现）是“严格要求正好装满重量 j”的基础上进行的，所以 dp 的状态转移也是通过 boolean 操作，相当于对经典的 01 背包做了一个变种。实际上本题不需要进行这么大的改写。

以下是正常01背包的滚动数组解法。

dp 数组下标的含义：dp[j] 的含义是，给定容量为 j 的背包，能够得到的最大物品价值
dp 递推公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[j])
- 如果不选择当前元素 i，即是 dp[j]
- 如果选择当前元素，即是 dp[j-nums[i]] + nums[i]
dp 数组的初始化：不对 nums 提前排序
- dp[0] = 0
- 剩余值的初始化不影响第一次遍历时的 max 操作即可
dp 的遍历顺序：滚动数组，先物品（行）后重量（列）

class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums) % 2:return Falsetarget_sum = sum(nums) // 2dp = [0] * (target_sum + 1)for i in range(len(nums)):              for j in range(target_sum, -1, -1):     if j >= nums[i]:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])return dp[-1] == target_sum