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

题目：牛能和牛可乐的礼物
描述：众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？
p.s 礼物都很珍贵，所以不可以拆开算哦
示例1：输入：[1,2,3,4]，返回值：0
说明：他俩一个人拿1,4 。另一个人拿2,3
示例2：输入：[1,3,5]，返回值：1
说明：他俩一个人拿1，3.另一个人拿5

解法一：
思路分析：首先我们分析题目，该题主要意思是将所有收到的礼物，按照其价值量进行平均分配，但是在分配的过程中可能导致价值量不均，所以本题求解的是礼物价值和的最小差值。
——我们以实例一进行分析，也就是价值量分别是[1，2，3，4]，所以我们可以将1和4分配给一个人，将2和3分配给另一个人，这样两个人得到的礼物的价值量为5相等，所以两个人的最小差值为0。
——我们明白了题目的意思以后，下面开始进行分析，首先我们需要将总价值量进行计算，总价值量通过一个for循环可以轻松解决。接下来，我们需要定义一个dp对象，用来保存初始状态，因为我们需要设置两个指针，i和j，i从头开始遍历presentVec数组，j负责从len - 1开始循环，依次循环，调节记录价值量的状态，最后再通过一个for循环，将dp中表示为true的的变量减去，即可得到最终的结果。
实例分析：输入：[1,2,3,4]
图片说明
——实际上就是遵循动态规划的思想，假如一个人拿到的礼物是sum1的话，则另一个人就是sum - sum1，然后将二者进行做差就能得到最终的结果值。
Python核心代码为：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param presentVec int整型一维数组 每个礼物的价值
# @return int整型
#
class Solution:
    def maxPresent(self , presentVec ):
        # write code here
        sum1 = sum(presentVec)#计算数组的元素和
        dp = (sum1 // 2 + 1) * [False]#设置初始状态false
        dp[0] = True#将第一个变量设置为true
        for i in presentVec:#正向循环
            for j in range(len(dp) - 1,i - 1,-1):#反向循环
                dp[j] = dp[j] or dp[j-i]
        for i in range(len(dp)-1,0,-1):#将dpi表示为true的减去，就能得到最小值
            if dp[i]:
                return sum1-i-i
        return sum1

——在该算法中，需要使用for循环遍历presentVec数组的大小，还需要遍历dp数组的大小，dp数组的大小为总价值量除以2加1，所以其时间复杂度为 $O(N + M)$ ，M为总价值量。因为需要构造额外的内存空间，所以其空间复杂度为 $O(M)$ 。
解法二：
思路分析： 我们也可以在动态规划中使用队列进行分析，首先设置队列为q，设置 $f[i][j]$ 表示当前循环遍历到了第i件礼物，两组礼物价值之间的差值为j，因为此时j可能会出现负数下标的情况，所以需要将j的值加上一个偏移量，避免出现负号下标，假设，当前礼物的价值为 $val[i]$ ，当 $f[i][j]$ 为true时，就发生转移 $f[i + 1][j + val[i]] = f[i + 1][j - val[i]] = true$ ，在循环是否为真可以用队列实现，最后通过扫描数组寻找到最小的差值即可。
C++核心代码：

const int MAXN = 200020;
const int MID = 100010;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    bool vis[2][MAXN];
    queue<int> q[2];
    int maxPresent(vector<int>& presentVec) {
        // write code here
        int len = presentVec.size();//数组的大小
        memset(vis,0,sizeof(vis));//相当于复制字符
        int cur = 0;//cur初始化为0
        q[cur].push(MID);
        vis[cur][MID] = 1;//vis数组0，MID初始化为0
        for(int i = 0;i < len;++i){//设置一个i指针循环遍历
            const int val = presentVec[i];
            int nxt = cur^1;
            while(!q[nxt].empty()) //只要Q[nxt]不为空，就出队列
                q[nxt].pop();
            while(!q[cur].empty()) {
                int S = q[cur].front();//设S为Q[cur]的首位元素
                vis[cur][S] = 0;//初始化为0
                if(!vis[nxt][S - val]) //判断
                    vis[nxt][S - val] = 1,q[nxt].push(S - val);
                if(!vis[nxt][S + val]) 
                    vis[nxt][S + val] = 1,q[nxt].push(S + val);
                q[cur].pop();//出队列
            }
            cur ^= 1;
        }
        int ans = 1e9;
        for(int i = 0;i < MAXN;++i) 
            if(vis[cur][i]) 
                ans = min(ans,abs(i-MID));//存在，则计算最小值
      return ans;
    }
};

——因为在动态规划的过程中，需要循环遍历presentVec数组的长度，还需要判断队列是否为空，所以其时间复杂度为 $O(N)$ ，在内存方面，添加了一个二维数组vis和队列q，所以其空间复杂度为 $O(N)$ 。