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

题目描述
众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。
那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？
p.s 礼物都很珍贵，所以不可以拆开算哦

方法一：动态规划的方法

求解思路
对于本题目的求解，我们可以将此题目看成背包容量为总和的一半的01背包问题。我们要装两部分，并且这两部分之间的差值要尽可能的小。我们依次遍历数组，利用动态规划的思想尽力将背包填满，对于背包中剩余余量，我们可虑装或者不装，因此状态转移公式为：
dp[j]=max{dp[j],dp[j-present[i]]+present[i]}
根据以上描述，我们即可求出本问题的答案。

图片说明

解题代码

class Solution {
public:
    int maxPresent(vector<int>& present) {
        int mysum = 0; // 声明求和变量
        for(int i = 0; i < present.size(); i++)
            mysum += present[i]; // 求和
        int n = mysum / 2;
        vector<int> mydp(n + 1, 0); // 动态规划
        for(int i = 0; i < present.size(); i++)
        {
            for(int j = n; j >= present[i]; j--)
            {   //背包有余量，继续装入
                mydp[j] = max(mydp[j], mydp[j - present[i]] + present[i]); // 状态转移方程
            }
        }
        return abs(mysum - 2 * mydp[n]); // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：辅助数组dp[n],引入额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：递归的思想

求解思路
对于方法一，我们亦可以用递归的思想进行解决。对于第i个礼物，背包容量剩下为c，如果装不下，则子问题是(i-1,c)。如果装得下，则子问题为max{i-1,c-(i-1),c-present[i]}。据上述描述，我们即可得到本题的答案。

图片说明

解题代码

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 mysum = 0; // 声明求和
        for(int i = 0; i < presentVec.size(); i++)
            mysum += presentVec[i];
        int n = mysum / 2;
        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);
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：辅助数组dp[n][n]，因此空间复杂度为 $O$ ( $图片说明$ )