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

思路：

题目的主要信息：

• 给定一串数组，将数组分为两部分
• 要使两部分各自的和相差最小

两部分的值越接近于总和的一半，相差越小。

方法一：动态规划（01背包）
具体做法：
依据上面提到的性质，我们可以将这个问题看成一个01背包问题：背包容量为总和的一半，因此我们要装两部分，然后依次遍历数组，利用动态规划尽力将背包填满，最后相差结果就是总和减去背包中最大值的两倍，因为两部分一部分是背包中最大值比一半少了或者多了一点，另一部分就相应会比一半多了或者少了一点，二者之差岂不就是总和减去背包中最大值的两倍，再取绝对值。
而对于背包中还剩余余量j我们可以考虑装入或者不装入，那么转移公式就是.(具体01背包问题可以参考我写的牛客网-题解 | #01背包#

class Solution {
public:
    int maxPresent(vector<int>& presentVec) {
        int sum = 0;
        for(int i = 0; i < presentVec.size(); i++)
            sum += presentVec[i]; //礼物总和
        int n = sum / 2; //总和的一半为最大容量
        vector<int> dp(n + 1, 0); //
        for(int i = 0; i < presentVec.size(); i++){ //遍历数组
            for(int j = n; j >= presentVec[i]; j--){ //背包有余量，继续撞入
                dp[j] = max(dp[j], dp[j - presentVec[i]] + presentVec[i]); //取最大值
            }
        }
        return abs(sum - 2 * dp[n]);
    }
};

复杂度分析：

• 时间复杂度：，n为数组长度，m为数组元素总和的一半，两层循环
• 空间复杂度：，辅助数组dp

方法二：递归+空间记忆
具体做法：
上述01背包的思路也可以用递归解决，对于第i个礼物，容量剩下为c，如果可以装不下，则子问题是，如果装得下则，子问题是。
但是这个递归是树型递归，复杂度极高，我们用一个二维数组来记忆每次递归回来的值，就不用再重复计算低级子问题。

class Solution {
public:
    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;
    }
    int maxPresent(vector<int>& presentVec) {
        if(presentVec.size() == 1) //只有一个的情况
            return presentVec[0];
        int sum = 0;
        for(int i = 0; i < presentVec.size(); i++)
            sum += presentVec[i]; //礼物总和
        int n = sum / 2; //总和的一半为最大容量
        vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1));  //记忆前i个数，j容量时的最大值
        int maxe = recursion(presentVec.size(), n, presentVec, dp);
        return abs(sum - 2 * maxe);
    }
};

复杂度分析：

• 时间复杂度：，这里的不为数组大小，而是数组元素总和的一半，递归最坏相当于遍历整个矩阵
• 空间复杂度：，辅助矩阵dp为数组总和一半大小的边长