牛能和牛可乐的礼物

[编程题]牛能和牛可乐的礼物

热度指数：3796 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。

那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？

p.s 礼物都很珍贵，所以不可以拆开算哦

示例1

输入

[1,2,3,4]

输出

说明

他俩一个人拿1,4 。另一个人拿2,3

示例2

输入

[1,3,5]

输出

说明

他俩一个人拿1，3.另一个人拿5

备注:

单个礼物价值不超过100，礼物个数小于100，所有礼物总价值不超过10000

算法知识视频讲解

Python

DarryYoung

#
# 
(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背包问题，两个分组的值越接近总和一半差值越小，将总和一半看作背包的最大容量，每次放入的数字就是每次的体积，最后做差返回即可

发表于 2020-05-18 02:24:16 回复(0)