01 背包
文档讲解：代码随想录
题目链接：46. 携带研究材料（第六期模拟笔试）
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
暴力解法：每个物品都有放与不放两种状态，复杂度是2的n次方
动态规划：
dp[i][j] ：下标为[0,i]之间的物品，任取放进容量为j的背包里的最大价值
必须是把dp数组定义为答案，然后找递推关系，反推到起点，然后双循环搞定
dp[i][j]可以由哪几个方向推出来，当前背包的状态取决于放不放当前的物品i
不放物品i的最大价值：dp[i-1][j]
放物品i：dp[i-1][j-weight[i]] + value[i]
dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-weight[i]] + value[i] )
dp数组初始化
初始化很有讲究
由 dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-weight[i]] + value[i] )可以看出：dp[i][j]由它的左上方和正上方推出来的
所以要初始化第一行和第一列，dp[i][j]与它原来的值没有关联，所以初始化成什么值都可以
遍历顺序
两层for循环，一个遍历物品，一个遍历背包的容量
对于二维数组实现的01背包，两层for循环是可以颠倒的，先遍历物品还是先遍历背包都可以
当前元素是由正上方和左上方推导出来的，如果要求当前元素的值，一定要确定左上方有值，正上方有值
如果先遍历物品，再遍历背包，那么就是一行一行的遍历，满足上方和左上方有数据，所以这个遍历方式是可以的
如果先遍历背包，再遍历物品，那么就是一列一列的遍历，满足上方和左上方有数据，所以这个遍历方式也是可以的
所以，对于二维数组实现的01背包，无论先遍历背包还是物品，要求的格子的值，满足左上方和正上方都有值，所以两种遍历方式都可以
def backpack(M,N,space,value):
bp = [[0 for j in range(N+1)] for i in range(M)]
#第一列都是0，初始化第一行
for i in range(1,N+1):
if space[0] > i:
continue
else:
bp[0][i] = value[0]
#先遍历物品，再遍历背包
for i in range(1,M):
for j in range(1,N+1):
if space[i] <= j: #能放下i
bp[i][j] = max(bp[i-1][j],bp[i-1][j-space[i]]+value[i])
else:#不能放下i
bp[i][j] =bp[i-1][j]
return (bp[M-1][N])
M, N = map(int, input().split())
space = list(map(int, input().split()))
value = list(map(int, input().split()))
# 计算并输出结果
print(backpack(M, N, space, value))注意：dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-weight[i]] + value[i] ) 要保证[j-weight[i]]下标大于等于0才可以，也就是容量大于等于weight[i]，也就是说，只有当容量大于i所占的空间时，才会考虑放不放i的问题，反之，那么肯定不会放物品i
动态规划：01背包理论基础（滚动数组）
用一维数组实现01背包
用二维数组实现01背包：dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-weight[i]] + value[i] )
可以看出当前层的数值是由上一层推导出来的，是不是就可以把i-1的数据拷贝到第i层，直接在第i层上进行操作，不断覆盖原来的数据
dp[j]:容量为j的背包所能装的物品的最大价值是dp[j]
递推公式
不放物品i的状态就是dp[j]
放物品i：dp[j-weight[i]] + value[i]
dp[j] = max(dp[j] ,dp[j-weight[i]] + value[i] )
初始化
dp[0] = 0
应该初始化一个非0中的最小值，这样取最大值不会覆盖递归出来的数据
遍历顺序
放物品i：dp[j-weight] + value[i] 这样写是因为在二维数组中dp[i-1][j-weight]中一定是没有物品i的，并且给物品i额外保留了位置，
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15 容量为1的背包中对于放不放物品0的判断
dp[2] = dp[2 - weight[0]] + value[0] = 30 容量为2的背包中对于放不放物品0的判断，但是dp[2 - weight[0]]之前已经判断过是否加入0背包了，可能是加入的，这就会造成重复
倒叙遍历保证每个物品被添加一次
不太懂
416. 分割等和子集
文档讲解：代码随想录
题目链接：. - 力扣（LeetCode）
这是一个0、1背包问题
背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。
要注意题目描述中商品是不是可以重复放入。
即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。
要明确本题中我们要使用的是01背包，因为元素我们只能用一次。
回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。
那么来一一对应一下本题，看看背包问题如何来解决。
只有确定了如下四点，才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
以上分析完，我们就可以套用01背包，来解决这个问题了。
重量和价值一样，当背包正好装满之后，最大价值就是11，那么就是true
递推公式
dp[j] = max(dp[j] ,dp[j-num[i]] + num[i] )
初始化
dp[0] = 0
遍历顺序
和上题一样，是倒叙遍历
class Solution:
def canPartition(self, nums: List[int]) -> bool:
#先判断是不是奇数
if sum(nums) % 2!=0:
return False
sum_num = int(sum(nums)/2)
print(sum_num)
dp = [0] * (sum_num+1)
for i in nums:#遍历物品
for j in range(sum_num,i-1,-1):
dp[j] = max(dp[j],dp[j-i]+i) #j要大于等于i才有意义，但是不知道为什么j小于i时，没有报错
if dp[-1] == sum_num:
return True
else:
return False疑问：j要大于等于i才有意义，但是不知道为什么j小于i时，没有报错。只是结果会有问题
