46.携带研究材料
题目链接
讲解链接
动规五部曲：
1.dp数组及其下标含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。如图所示：
2.确定递推公式： 从物品i是否放进背包两个角度来考虑。
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.dp数组如何初始化：首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。而从状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
4.确定遍历顺序：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向）虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！
5.举例推导dp数组：背包最大重量为4。物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
dp数组为：
代码如下：
def bag_problem(weights, values, bag):
dp = [[0] * (bag + 1) for _ in range(len(weights))] # 初始化dp数组全为0
for j in range(weights[0], bag + 1): # 初始化存放物品0的时候背包中的价值
dp[0][j] = values[0]
for i in range(1, len(weights)): # 先遍历物品
for j in range(bag + 1): # 再遍历背包
if j < weights[i]: # 放不下第i个物品
dp[i][j] = dp[i - 1][j] # 则与上一行的dp值相等
else: # 若能放入第i个物品
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]) # 背包放物品i得到的最大价值
return dp[-1][-1]本题也可以用一维的dp数组（滚动数组）进行实现。
动规五部曲：
1.dp数组及下标含义：在二维dp数组的情况下，dp数组的含义是从[0,i]的物品中任意取装入容量为j的背包中能够获得的最大价值总和。那么在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2.确定递推公式：dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示容量为 j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，所以递归公式为：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
3.dp数组初始化：dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。因为递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 所以dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0即可。
4.dp数组遍历顺序：二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。因为倒序遍历是为了保证物品i只被放入一次！。如果一旦正序遍历，那么物品0就会被重复加入多次。
5.举例推导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]416.分割等和子集
题目链接
讲解链接
思路：找到集合里能够出现 sum / 2 的子集总和，就可以分割成两个相同元素和子集。本题需要把01背包的思路套上来：
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
动规五部曲：
1.dp数组及其下标含义：本题中每一个元素的数值既是重量，也是价值。dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以当 dp[target] == target 时，说明背包装满。
2.确定递推公式：01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);本题则相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式为：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.dp数组初始化：全部初始化为0即可；
4.确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历；
5.举例推导dp数组：dp[j]的数值一定是小于等于j的。如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
dp = [0] * 10001 # 初始化为全零，因为总和不超过20000，所以设置sum/2的值就可以
if sum(nums) % 2 == 1: # 如果和为奇数，说明不可能分割成两个等和子集
return False
target = sum(nums) // 2 # 目标值为sum/2
for i in nums: # 先遍历物品
for j in range(target, i - 1, -1): # 再倒序遍历背包
dp[j] = max(dp[j], dp[j - i] + i)
if dp[target] == target:
return True
else:
return False
