01背包理论（二维数组）
对于面试来讲，其实掌握01背包和完全背包已经完全够用了；而完全背包也是01背包稍作变化而来的，所以背包问题的理论基础的重中之重就是01背包，一定要理解透彻；
01背包将背包容量、价值填写在二维表格中，进行动态规划的思路，便于理解，dp[i][j]；
46. 携带研究材料（第六期模拟笔试）
n, bagweight = map(int, input().split())weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [[0]*(bagweight+1) for _ in range(n)]for j in range(weight[0], bagweight+1):dp[0][j] = value[0]for i in range(1, n):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])
print(dp[n-1][bagweight])01背包理论（一维dp数组（滚动数组））
对于背包问题其实状态是可以进行压缩的；
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把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]（一维数组，也可以理解是一个滚动数组）。
46. 携带研究材料（第六期模拟笔试）
n, bagweight = map(int, input().split())weight = list(map(int, input().split()))
value = list(map(int, input().split()))
# 创建一个动态规划数组dp，初始值为0
dp = [0] * (bagweight+1)
# 初始化do[0]=0，背包容量为0， 价值最大为0
dp[0] = 0
# 先遍历物品，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品
for i in range(n):# 倒序遍历背包容量是为了保证物品i只被放入一次for j in range(bagweight, weight[i] - 1, -1):dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
print(dp[bagweight])416. 分割等和子集 - 力扣（LeetCode）
使用01背包的方法，但是需要进行一些判断才能把01背包的问题套到本题上
1、背包的体积为sum / 2
2、背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
3、背包如果正好装满，说明找到了总和为 sum / 2 的子集。
4、背包中每一个元素是不可重复放入。
以上分析完，我们就可以套用01背包，来解决这个问题了。
①确定dp数组以及下标的含义
dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]；那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。
②确定递推公式
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
③dp数组如何初始化
本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
④确定遍历顺序
如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
⑤举例推导dp数组
dp[j]的数值一定是小于等于j的。如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。
用例1，输入[1,5,11,5] 为例，如图：
最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。
from typing import List
class Solution:def canPartition(self, nums: List[int]) -> bool:total_sum = sum(nums)if total_sum % 2 != 0:return Falsetarget_sum = total_sum // 2dp = [[False]*(target_sum+1) for _ in range(len(nums)+1)]# 初始化第一行（空子集可以得到和为0）for i in range(len(nums)+1):dp[i][0] = Truefor i in range(1, len(nums)+1):for j in range(1,target_sum+1):if j < nums[i-1]:# 当前数字大于目标和时，无法使用该数字dp[i][j] = dp[i-1][j]else:# 当前数字小于等于目标时，可以选择使用或不使用该数字dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]return dp[len(nums)][target_sum]if __name__ == '__main__':nums = [1,5,11,5]res = Solution().canPartition(nums)print(res)