【最全背包九讲】

搜了一下发现网上python类的背包问题讲的不太清楚，于是打算自己写一份详细有注释的。

先介绍动态规划类的五部曲

1. 确定dp数组以及下标的含义：
2. 确定递推公式
3. 初始化
4. 确定遍历顺序，哪个在内哪个在外，顺序还是倒叙遍历
5. 举例验证。

1. 0/1背包采用外层物品，内层循环背包。
2. 我们使用了一维数组代替二维数组，由于背包每个物品只能放一次，所以内层背包循环必须逆序。

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

题目目标和，指路

bagSize = (sumValue + target) // 2
dp = [0] * (bagSize + 1)
dp[0] = 1
for i in range(len(nums)):
    for j in range(bagSize, nums[i] - 1, -1):
        dp[j] += dp[j - nums[i]]
return dp[bagSize]

#分割子集和，是一个对错问题
dp=[False]*(t+1)
dp[0]=True
for i in range(len(nums)):
    for j in range(t,nums[i]-1,-1):
        dp[j]=dp[j] or dp[j-nums[i]]

二维数组

dp = [[0] * (n + 1) for _ in range(m + 1)]	# 默认初始化0
# 遍历物品
for str in strs:
    ones = str.count('1')
    zeros = str.count('0')
    # 遍历背包容量且从后向前遍历！
    for i in range(m, zeros - 1, -1):
        for j in range(n, ones - 1, -1):
            dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
return dp[m][n]