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

文章目录卡码网46. 携带研究材料0-1背包问题二维思路解答0-1背包问题一维思路解答LeetCode416. 分割等和子集思路解答卡码网46. 携带研究材料https://kamacoder.com/problempage.php?pid10460-1背包问题二维思路定义dp[i][j]表示只考虑前i件物品索引从0到i在背包容量为j时能获得的最大价值。最终目标为dp[n-1][bag]。状态转移方程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件的价值。初始化所有dp[i][j]初始化为0。解答first_lineinput().split()nint(first_line[0])bagint(first_line[1])second_lineinput().split()third_lineinput().split()weight[int(x)forxinsecond_line]value[int(x)forxinthird_line]dp[[0]*(bag1)for_inrange(n)]forjinrange(weight[0],bag1):dp[0][j]value[0]foriinrange(1,n):forjinrange(bag1):ifjweight[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背包问题一维思路定义dp[j]表示当前考虑的物品范围内背包容量为j时能获得的最大价值。状态转移方程dp[j] max(dp[j], dp[j - w] v) (j w)。初始化dp [0] * (bag 1)。解答first_lineinput().split()nint(first_line[0])bagint(first_line[1])second_lineinput().split()third_lineinput().split()weight[int(x)forxinsecond_line]value[int(x)forxinthird_line]dp[0]*(bag1)# dp[j] 表示容量 j 能获得的最大价值foriinrange(n):wweight[i]vvalue[i]# 逆序遍历保证每种物品只选一次forjinrange(bag,w-1,-1):dp[j]max(dp[j],dp[j-w]v)print(dp[bag])LeetCode416. 分割等和子集https://leetcode.cn/problems/partition-equal-subset-sum/description/添加链接描述思路转化为01-背包问题每个元素只能选或不选背包容量为target求是否能恰好装满。解答classSolution:defcanPartition(self,nums:List[int])-bool:totalsum(nums)# 总和为奇数则无法平分iftotal%2!0:returnFalsetargettotal//2nlen(nums)# dp[j] 表示当前已考虑的元素能否凑出和为 jdp[False]*(target1)dp[0]Truefornuminnums:# 从后往前更新避免重复使用当前元素forjinrange(target,num-1,-1):dp[j]dp[j]ordp[j-num]returndp[target]