背包问题0-1背包
0-1背包是每个物品只能使用一次；
完全背包每个物品可以无限次使用；
0-1背包
二维dp数组
- dp[i][j]下标为0-i之间的物品任意取放进背包为j的背包里
- 不放物品i表示dp[i-1][j]; 放物品i变成dp[i-1][j - weight[i]] + value[i] 最后取两者最大值
- 初始化
- 遍历顺序：两层for循环，二维dp数组实现的都可以交换循序，
题目链接
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
解题思路
容量为sum(nums // 2)的背包可以装满吗
每个元素只能使用一次
- dp[j]表示的含义是，容量为j的背包最大价值为dp[j]
- 背包装满的表达式为dp[target] = target
- dp[j] = max(dp[j], dp[j - weight[j]] + value[i])其实是二维数组的状态压缩
- 初始化：dp[0] = 0 dp其他初始化0
- 遍历顺序，01背包的遍历顺序，遍历物品，背包，因为进行了状态压缩，所以不可以交换顺序。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
target = sum(nums)
if target % 2 == 1: return False
target //= 2
dp = [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])
return target == dp[target]
感觉这个二维数组压缩成一维数组没太看懂
