【代码随想录算法训练营第四十天|卡码网46.携带研究材料，416.分割等和子集】

卡码网46.携带研究材料

这题是01背包问题。

二维dp数组

dp数组[i][j]前一位表示的是物品的种类，后一位表示的是背包的容量，在物体为i时，容量为j的背包的最大价值由不放入i的dp[i-1][j]和放入i的dp[i-1][j-spaces[i]]+values[i]中的最大值所决定，当然这是在容量大于spaces[i]时才能实现，小于spaces[i]的时候则只能维持dp[i-1][j]的数值。最终的最大价值就是由二维dp数组最右下角的值决定。

s = input().split()
M, N = int(s[0]), int(s[1])
spaces = list(map(int, input().split()))
values = list(map(int, input().split()))
dp = [[0 for _ in range(N+1)] for _ in range(M)]
for i in range(spaces[0], N+1):
    dp[0][i] = values[0]
for i in range(1, M):
    for j in range(N+1):
        if j < spaces[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-spaces[i]]+values[i])
print(dp[M-1][N])

一维dp数组（滚动数组）

其实就是上面的二维dp在物品维度压缩，只留下背包层。但是这样就必须要先物品后背包（不然一直都是同一个物品（物品1）在遍历），然后在遍历背包的时候还要注意只能倒序遍历，如果正序的化，前面的数据如果已经添加了该物品，则会重复添加（因为二维dp的时候用的时上一层的数据，不会出现覆盖而重复添加）。

s = input().split()
M, N = int(s[0]), int(s[1])
spaces = list(map(int, input().split()))
values = list(map(int, input().split()))

dp = [0 for _ in range(N+1)] 
for i in range(spaces[0], N+1):
    dp[i] = values[0]

for i in range(1, M):
    for j in range(N, spaces[i]-1, -1):
            dp[j] = max(dp[j], dp[j-spaces[i]]+values[i])

print(dp[N])

416.分割等和子集

能够分割出两个等和的子集，说明子集的合都是整个数组总和的一半。所以如果数组总和为奇数直接返回False。
然后就是找是否有子集能够使得和为数组和的一半target，令dp[i]数组表示和上限为i的时候，数组可以选出的最大子集和，当dp索引为target的时候如果值也为target那么就是可以满足条件。
那么问题就成了一个背包大小为target，各个物品价值为nums对应值的01背包问题，和上一题解法一致。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ & 1:
            return False
        target = sum_ >> 1
        dp = [0 for _ in range(target+1)]
        for j in range(nums[0], target+1):
            dp[j] = nums[0]
        for i in nums[1:]:
            for j in range(target, i-1, -1):
                dp[j] = max(dp[j], dp[j-i]+i)
        return dp[target] == target