题解 | 牛能和牛可乐的礼物

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param presentVec int整型一维数组 每个礼物的价值
# @return int整型
#
class Solution:
    def maxPresent(self , presentVec ):
        # write code here
        total = sum(presentVec)
        cap = total // 2
        dp = [0] * (cap + 1)
        for gift in presentVec:
            for j in range(cap, gift - 1, -1):
                if dp[j] < dp[j - gift] + gift:
                    dp[j] = dp[j - gift] + gift
        
        return total - 2 * dp[cap]