牛能和牛可乐的礼物

//方法一：
//这种方法也就是暴力搜索了，先对整个数组进行排序，差值最小，确认数组长度n，
//肯定先从数组末尾开始找，如若数组末尾数大于前n-1项和，则停止搜索，否则加上数组最小的数值，在对其他项相加求和，进行比较
//以此类推：
//文字有些难以理解，举个简单的例子[1，2，3，4，5],第一步：5<1+2+3+4;第二步：5+1<4+3+2；第三步：5+1+2>4+3;最后最小差值
//就为8-7=1；但是这个代码好像比较low，只能通过用例，不能a，哈哈；
class Solution {
public:
    /*
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int Sum_Array(vector<int>&presentVec,int a,int b){
        int sum=0;
        for(int i=a;i<b;i++){
            sum+=presentVec[i];
        }
        return sum;
    }
    int maxPresent(vector<int>& presentVec) {
        // write code here
        int n=presentVec.size();
        if(presentVec.size()==2)return abs(presentVec[0]-presentVec[1]);
        int sumA=0;
        int sumB=presentVec[n-1];
        sort(presentVec.begin(),presentVec.end());
        for(int i=0;i<n-1;i++){
            sumA+=presentVec[i];
        }
        if(sumB>=sumA)return sumB-sumA;
        else{
            for(int i=0;i<n-1;i++){
                sumB+=presentVec[i];
                sumA=Sum_Array(presentVec,i+1,n-1);
                if(sumB>=sumA)return sumB-sumA;
            }
        }
    }
};
//方法2：这个方法就比较巧妙了，还是借鉴牛客上其他大佬的思路，写出来的，理解了就好，代码挺简单的
//01背包问题，两个分组的值越接近总和一半差值越小，
//将总和一半看作背包的最大容量，每次放入的数字就是每次的体积，最后做差返回即可
class Solution{
public:
    int maxPresent(vector<int>& presentVec) {
        int sum=0;
        for(auto num:presentVec){
            sum+=num;
        }
        int split_sum=sum/2;
        vector<int>dp(split_sum+1,0);
        for(int i=0;i<presentVec.size();i++){
            for(int j=split_sum;j>=presentVec[i];j--){
                dp[j]=max(dp[j],dp[j-presentVec[i]]+presentVec[i]);
            }
        }
        return (sum-2*dp[split_sum]);//你仔细品，哈哈
    }
};

class Solution {
public:
    /**
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        int s = 0;
        for(auto &x: presentVec)
            s += x;
        int V = s/2, dp[V+1];
        memset(dp, 0, sizeof(dp));
        for(auto &x: presentVec)
            for(int j=V;j>=x;j--)
                dp[j] = max(dp[j], dp[j-x]+x);
        return abs(s-2*dp[V]);
    }
};

#
# 
(5842)# @param presentVec int整型一维数组 每个礼物的价值
# @return int整型
(5843)#
class Solution:
    def maxPresent(self , presentVec ):
        # write code here
        s = sum(presentVec)
        bv = s//2 + 1
        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 - dp[bv-1] - dp[bv-1]

int maxPresent(vector<int>& presentVec) {
        int sum = 0,size=presentVec.size();
        for(int i=0;i<size;i++)sum+=presentVec[i];
        vector<int>dp(sum/2+1,0);
        for(int i=0;i<size;i++){
            for(int j=sum/2;j>=presentVec[i];j--){
                dp[j] = max(dp[j],dp[j-presentVec[i]]+presentVec[i]);
            }
        }
        int res=2*dp[sum/2]-sum;
        return res>=0?res:-res;
    }

• 将问题转化为0-1背包问题来解决
• 思路：我们取礼物价值总和数的一半（向上取）来作为我们背包的容量，我们要尽可能地去填满这个背包，这样差值就是最小

import java.util.*;
public class Solution {
    /**
     * 
     * @param presentVec int整型一维数组 每个礼物的价值
     * @return int整型
     */
    public int maxPresent (int[] presentVec) {
        // write code here
        int n = presentVec.length;
        if(n == 0) return 0;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += presentVec[i];
        }
        //简化为背包问题
        int v = (sum + 1) / 2;
        int[] dp = new int[v+1];
        for(int i = 0; i < n; i++){
            int p = presentVec[i];
            for(int j = v; j >= p; j--){
                dp[j] = Math.max(dp[j], dp[j-p]+p);
            }
        }
        int result = 2*dp[v] - sum;
        return  result >= 0 ? result : -result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param presentVec int整型一维数组 每个礼物的价值
     * @return int整型
     * 典型的01背包问题
     */
    public int maxPresent (int[] presentVec) {
        // write code here
        int sum = 0;
        int value = 0;
        for (int i = 0; i < presentVec.length; i++){
            sum = sum+ presentVec[i];
            value = sum/2;
        }
        int[][] dp = new int[presentVec.length+1][value+1];
        for (int i = 1; i < presentVec.length+1; i++){
            for (int j = 1; j < value + 1; j++){
                if (presentVec[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }else if (presentVec[i-1] == j){
                    dp[i][j] = Math.max(presentVec[i-1], dp[i-1][j]);
                }else{
                    dp[i][j] = Math.max(dp[i-1][j-presentVec[i-1]]+presentVec[i-1], dp[i-1][j]);
                }
            }
        }
        int result = (sum - dp[presentVec.length][value]) - dp[presentVec.length][value];
        if (result < 0){
            return 0-result;
        }else{
            return result;
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param presentVec int整型一维数组 每个礼物的价值
     * @return int整型
     */
    public int maxPresent (int[] presentVec) {
        // write code here
        int n = presentVec.length;
        if(n == 0){
            return 0;
        }
        //求礼物总和
        int sum = 0;
        for(int i = 0; i < n;i++){
            sum += presentVec[i];
        }
        
        int v = sum / 2;
        int[] dp = new int[v+1];
        for(int i = 0; i < n;i++){
            for(int j = v;j >= presentVec[i];j--){
                dp[j] = Math.max(dp[j], dp[j-presentVec[i]]+presentVec[i]);
            }
        }
        
        int res = 2 * dp[v] - sum;
        return res >= 0 ? res : -res;
    }
}

class Solution:
    def maxPresent(self , p ):
        # write code here
        if len(p) <= 0:
            return 0
        p.sort()
        pa = sum(p)
        if len(p) < 2:
            return p[0]
        dp = [[0 for i in range(pa+1)] for j in range(len(p))]
        dp[0][p[0]] = 1
        dp[0][0] = 1
        f = p[0]
        for i in range(1,len(p)):
            for j in range(f+1):
                dp[i][j] += dp[i-1][j]
                dp[i][j+p[i]]  = dp[i][j+p[i]] + 1 if dp[i-1][j] != 0 else 0
            f += p[i]
        res = dp[-1]
        m = pa
        for i in range(pa):
            if res[i] != 0:
                m = min(m,abs((pa-i)-i))
        return m