46. 携带研究材料（第六期模拟笔试）
背包问题（二维dp数组）
其中最基础的就是0-1背包问题，也就是每个物品实际上只有1个，只有取与不取两种状态。所以理论上来讲，可以通过暴力+判断的办法穷举所有可能性。
更进一步的，如果考虑基于前一次操作（放入物品）和状态（背包剩余容量），就可以给出基于动态规划的解法，因为实际上就是在做递推。
1、dp数组初始化。
初始化需要解决2个问题，意思就是确定下标和值的含义。本题涉及到两种下标，背包的剩余容量和物品是否放进去。值就是背包当前的最大价值。不难初始化如下图所示：
其中，dp由一个二维数组构成，其中行为物品编号，列为背包剩余容量，值为当前确定的最大价值。
初始化。此时的数组只能根据第一个值进行初始化。也就是：
（1）第一列j=0，此时背包剩余容量为0，放不了任何物品，价值dp = 0；
（2）根据第1个物品（行=0）初始化第一行：判断如果背包容量>=物品0的重量，则后面列都是value[0]，也就是都是第一个物品的价值。
2、确定递推公式
假设当前的数组为dp[i][j]，想求最大的价值，则需参考前一步的价值进行判断：
（1）之前说了，对于每一个物品都有取和不取两种操作。对于不取第i个物品，则当前的背包容量和价值维持上一个物品操作后的dp状态和值，也就是dp[i-1][j]。对应的是当前行的上一行、同一列的dp值：
（2）还有一种情况是，取了当前的物品，那么此时背包的容量和值都会发生更改。假设上一次的值为dp[i-1][j-weight[i]]，其中j-weight[i]表示还没取当前物品的背包剩余空间，也就对应的是上一行，j-weight[i]列的值：
综上即可得出递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。
3、确定遍历顺序
由于当前的遍历顺序都是先便利行（物品）再便利列（背包容量）的，所以先i后j。
4、更新dp。
根据之前确定好的递归公式确定更新后的dp数组。
n, weight, val = [int(x) for x in (input().split())], [int(x) for x in (input().split())], [int(x) for x in (input().split())]
num, bagweight = n[0], n[1]dp = [[0]* (bagweight+1) for _ in range(num)] # bagweight需要从0开始for j in range(weight[0], bagweight+1):dp[0][j] = val[0]for i in range(1, num):for j in range(1, bagweight+1):if j >= weight[i]:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+val[i])else:dp[i][j] = dp[i-1][j]print(dp[num-1][bagweight])背包问题（一维dp数组）
如果观察二维的数组的更新过程可以发现，下一层的数组完全取决于上一层的数组的值，跟其他的位置没有关系。所以在更新下一行的数组的时候，可以直接把上一行的数组拷贝下来。每一步和上面二维数组的有一些区别。
1、确定dp数组的含义
dp数组的每一个dp[j]代表当前容量的最大价值。
2、确定递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，相当于把i的维度压缩了。
3、初始化
由于递推公式仅取决于当前物品，且取最大值，所以不用担心初始化的问题，全部设置为0就好。
4、确定遍历顺序
和之前二维数组从小到大遍历背包顺序不同，一维数组需要从大到小遍历背包容量。
num, bagweight = map(int, input().split())
weight = [int(x) for x in input().split()]
value = [int(x) for x in input().split()]dp = [0] * (bagweight + 1)for i in range(num):for j in range(bagweight, -1, -1): # 注意是从大到小遍历背包空间if j >= weight[i]:dp[j] = max(dp[j], dp[j-weight[i]] + value[i])else:continueprint(dp[-1])416. 分割等和子集
本题在原来0-1背包的基础上做了一些变化：
1、没有给出背包容量。背包容量实际上就是集合元素之和除以2的target，如果能够恰好装满这个容量，那么就说明能够实现分割；
2、没有给出物品的重量和价值。实际上数字的重量和价值都等于数字本身；
3、初始化。由于都是正整数，且更新dp采用的是max操作，所以最好初始化为0.
采用一维dp进行求解，注意内层j遍历从大到小。
1、确定dp数组大小和含义。大小由target = sum /2 确定，相当于是背包的容量。dp的值就相当于是当前的数字和；
2、初始化。dp由于全部都是正整数，所以初始化为0即可；
3、确定递推公式。在0-1背包的一维数组解法中将weight和value统一成nums的值即可。
4、确定遍历顺序。两层，外层i遍历nums，内层j从大到小从target到nums[i]遍历背包容量。
class Solution(object):def canPartition(self, nums):""":type nums: List[int]:rtype: bool"""if sum(nums) % 2 == 1:return Falsetarget = sum(nums) / 2dp = [0] * (target + 1)for i in range(len(nums)):for j in range(target, nums[i]-1, -1):dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]) # nums[i]看作重量和价值相等return True if dp[-1] == target else False第40天完结！！！