牛能和牛可乐的礼物

• 将问题转化为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;
    }
}