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])
dp[i][j]表示从前i个物品中选择，放入容量为j的书包，拥有的最大价值。
对应dp数组如下：
| 物品可选数量 \ 背包容量 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | - | - | - | - |
| 1 | - | - | - | - |
| 2 | - | - | - | - |
46. 携带研究材料（第六期模拟笔试）
n, bagweight = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [0] * (bagweight + 1)for i in range(n):for j in range(bagweight, weight[i] - 1, -1):dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagweight])
这里倒序是为了遍历不覆盖上一次的数据，并且重量只需要遍历到weight[i]就行了，不需要遍历到零，因为这个是背包的容量，背包的容量小于i物品的重量，那么他能放的东西也只到i-1，上次的状态（数据）不会更新。
416. 分割等和子集
class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums) % 2 != 0:return Falsehalf = sum(nums) // 2dp = [0] * (half + 1)for numi in nums:for j in range(half, numi - 1, -1):dp[j] = max(dp[j], dp[j - numi] + numi)return dp[half] == half
有点抽象，那容量为一半的背包去装，如果能装满，说明符合条件。那么背包容量就应该是half，装满的情况是：dp[half] == half。
