[算法][动态规划]背包问题：均分礼物
发布时间
阅读量：
阅读量
均分礼物
今日在面试过程中遭遇的一道编程题目如下：
提供一份包含礼物价值的列表，要求将其拆分为两个子集，目标是使这两个子集的价值总和之间的差异达到最小化。
思路
[[算法][动态规划][背包问题①]0-1背包问题的优化及约束变形python实现
- 可以将其归类为0-1背包问题进行处理
- 将整体价值总量的一半设定为背包的最大承载能力
- 尽可能地将物品装入该背包中（在本问题中，物品的重量w_i与价值v_i相等）
dp[j]=max\{dp[j−w_i]+v_i ,dp[j]\}
- 最终结果可通过将整体价值减去半容量背包所获得的最大价值得出
代码
class Solution:
def maxPresent(self , presentVec):
# 把总体积的一半作为背包容量
all_volume = sum(presentVec)
half_volume = all_volume//2
dp = [0] * (half_volume+1)
for w in presentVec:# 第i个物品
for j in range(half_volu全部评论 (0)
还没有任何评论哟~