算法思想一：动态规划

解题思路：

将问题转换为01背包问题，两个分组的值越接近总和一半差值越小，将总和一半看作背包的最大容量，每次放入的数字就是每次的体积，最后做差返回即可
定义dp数组，其中表示背包空间为 i 时装物品的最大价值：
  • :背包容量 j 装不下第个礼物装不下，继承的值
  • 背包容量 j 装得下第个物品在装下与装不下中选择最大值
即

图解：

代码展示：

Python版本 

class Solution:
    def maxPresent(self , presentVec ):
        # write code here
        # 数组总和
        s = sum(presentVec)
        # 计算最多选礼物数量
        bv = s//2 + 1
        # dp数组
        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 - 2 * dp[bv-1]

复杂度分析

时间复杂度：N表示数组的长度，第一次遍历时间，第二次遍历时间，求和计算时间，最后为

空间复杂度：dp数组占用空间

算法思想二：递归

解题思路：

对于方法一，可以用递归的思想进行解决。对于第 i 个礼物，背包容量剩下为 capacity，如果装不下，则子问题是。如果装得下，则子问题为。
据上述描述进行递归计算，即可得到本题的答案。

代码展示：

C++版本 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        // write code here
        if(presentVec.size() == 1) // 只有一个的情况
            return presentVec[0];
        int mysum = 0; // 声明求和
        // 计算总价值
        for(int i = 0; i < presentVec.size(); i++)
            mysum += presentVec[i];
        int n = mysum / 2;
        // dp数组
        vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1));
        int max = recursion(presentVec.size(), n, presentVec, dp); // 更新max用于计算最终答案
        return abs(mysum - 2 * max);
    }
    // 递归函数
    int recursion(int n, int capacity, vector<int>& presentVec, vector<vector<int>>& dp)
    {
        // 特殊情况
        if (n <= 0 || capacity == 0)
        {
            dp[n][capacity] = 0; // 初始条件
            return 0;
        }
        else if(presentVec[n - 1] > capacity)
        {
            if(dp[n - 1][capacity] == -1) // 装不下
                dp[n - 1][capacity] = recursion(n - 1, capacity, presentVec, dp);
            return dp[n - 1][capacity]; // 返回局部值
        }
        else
        {   //可以装下的情况
            if(dp[n - 1][capacity] == -1)
                dp[n - 1][capacity] = recursion(n - 1, capacity, presentVec, dp);
            if(dp[n - 1][capacity - presentVec[n - 1]] == -1)
               dp[n - 1][capacity - presentVec[n - 1]] = recursion(n - 1, capacity - presentVec[n - 1], presentVec, dp);
            dp[n][capacity] = max(dp[n - 1][capacity], dp[n - 1][capacity - presentVec[n - 1]] + presentVec[n - 1]);
            // 返回子问题结果
            return dp[n][capacity];
        }
        return 0;
    }
};

复杂度分析

时间复杂度：N表示数组的长度，最差情况下递归遍历整个dp数组时间

空间复杂度：dp数组占用空间