众所周知,牛能和牛可乐经常收到小粉丝们送来的礼物,每个礼物有特定的价值,他俩想要尽可能按照自己所得价值来平均分配所有礼物。
那么问题来了,在最优的情况下,他俩手中得到的礼物价值和的最小差值是多少呢?
p.s 礼物都很珍贵,所以不可以拆开算哦
[1,2,3,4]
0
他俩一个人拿1,4 。另一个人拿2,3
[1,3,5]
1
他俩一个人拿1,3.另一个人拿5
单个礼物价值不超过100,礼物个数小于100,所有礼物总价值不超过10000
# # (5842)# @param presentVec int整型一维数组 每个礼物的价值 # @return int整型 (5843)# class Solution: def maxPresent(self , presentVec ): # write code here s = sum(presentVec) bv = s//2 + 1 dp = [0]*bv for i in range(len(presentVec)): for j in range(bv-1, presentVec[i]-1, -1): dp[j] = max(dp[j], dp[j-presentVec[i]] + presentVec[i]) return s - dp[bv-1] - dp[bv-1]01背包问题,两个分组的值越接近总和一半差值越小,将总和一半看作背包的最大容量,每次放入的数字就是每次的体积,最后做差返回即可