【Day30】卡码网：46. 携带研究材料，LeetCode：416. 分割等和子集

卡码网：46. 携带研究材料

https://kamacoder.com/problempage.php?pid=1046

0-1背包问题，二维

思路

1. 定义：dp[i][j]表示只考虑前i件物品（索引从0到i），在背包容量为j时能获得的最大价值。最终目标为dp[n-1][bag]。
2. 状态转移方程：
   （1）当j < weight[i]（当前容量放不下第i件物品）时：
   dp[i][j] = dp[i-1][j]，即不选第i件，结果与前i - 1件相同。
   （2）当j >= weight[i]（可以放下第i件物品）时：
   dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
   不选：价值为dp[i-1][j]；
   选：先腾出weight[i]的空间（j - weight[i]），加上第i件的价值。
3. 初始化：所有dp[i][j]初始化为0。

解答

first_line=input().split()n=int(first_line[0])bag=int(first_line[1])second_line=input().split()third_line=input().split()weight=[int(x)forxinsecond_line]value=[int(x)forxinthird_line]dp=[[0]*(bag+1)for_inrange(n)]forjinrange(weight[0],bag+1):dp[0][j]=value[0]foriinrange(1,n):forjinrange(bag+1):ifj<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][bag])

0-1背包问题，一维

思路

1. 定义：dp[j]表示当前考虑的物品范围内，背包容量为j时能获得的最大价值。
2. 状态转移方程：dp[j] = max(dp[j], dp[j - w] + v) (j >= w)。
3. 初始化：dp = [0] * (bag + 1)。

解答

first_line=input().split()n=int(first_line[0])bag=int(first_line[1])second_line=input().split()third_line=input().split()weight=[int(x)forxinsecond_line]value=[int(x)forxinthird_line]dp=[0]*(bag+1)# dp[j] 表示容量 j 能获得的最大价值foriinrange(n):w=weight[i]v=value[i]# 逆序遍历，保证每种物品只选一次forjinrange(bag,w-1,-1):dp[j]=max(dp[j],dp[j-w]+v)print(dp[bag])

LeetCode：416. 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/description/
添加链接描述

思路

转化为01-背包问题：每个元素只能选或不选，背包容量为target，求是否能恰好装满。

解答

classSolution:defcanPartition(self,nums:List[int])->bool:total=sum(nums)# 总和为奇数则无法平分iftotal%2!=0:returnFalsetarget=total//2n=len(nums)# dp[j] 表示当前已考虑的元素能否凑出和为 jdp=[False]*(target+1)dp[0]=Truefornuminnums:# 从后往前更新，避免重复使用当前元素forjinrange(target,num-1,-1):dp[j]=dp[j]ordp[j-num]returndp[target]