01背包问题 二维
1. 确定dp数组以及下标的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2. 确定递推公式
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[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
4. 确定遍历顺序
有两个遍历的维度：物品与背包重量，遍历哪个都可以
5. 举例推导dp数组
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 = 4
result = test_2_wei_bag_problem1(weight, value, bagweight)
print(result)01背包问题 一维
可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
1. 确定dp数组的定义
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
2. 一维dp数组的递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
3. 一维dp数组如何初始化
假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了
4. 一维dp数组遍历顺序
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？不可以！因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
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]
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
bagweight = 4
result = test_1_wei_bag_problem(weight, value, bagweight)
print(result)416. 分割等和子集
套用01背包
背包的体积为sum / 2。背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值。背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 确定dp数组以及下标的含义：dp[j]表示容量为j的背包，所背物品的最大价值可以为dp[j]。套到本题，dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。
- 确定递推公式：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
- dp数组初始化：本题题目中只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
- 确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
- 举例推导dp数组
class Solution:
def canPartition(self, nums: List[int]) -> bool:
_sum = sum(nums)
if _sum % 2 == 1:
return False
dp = [0] * (_sum//2 + 1)
for num in nums:
for j in range(_sum//2, num-1, -1):
dp[j] = max(dp[j], dp[j-num] + num)
return dp[_sum//2] == _sum//2
稍微简化写法
class Solution:
def canPartition(self, nums: List[int]) -> bool:
_sum = sum(nums)
if _sum % 2 == 1:
return False
target = _sum//2
dp = [0] * (target + 1)
for num in nums:
for j in range(target, num-1, -1):
dp[j] = max(dp[j], dp[j-num] + num)
return dp[target] == target
