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

解题思路：
1. 01背包问题
2. 背包容量为总额的一半

class Solution:
    def maxPresent(self , presentVec ):
        """ 01 背包 """
        if len(presentVec) == 0:
            return 0

        sum_pre = sum(presentVec)
        sum_vec = int(sum_pre // 2) + 1  # 背包的容量

        # 初始化
        dp = [0 for i in range(sum_vec)]

        # 动态转移方程 dp[i][j] = dp[i-1][j-presentVec[i]] + arr[i]
        for i in range(len(presentVec)):
            for j in range(sum_vec - 1, presentVec[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - presentVec[i]] + presentVec[i])

        return int(abs(sum_pre - 2 * dp[-1]))