/**
 * @param n 背包容量
 * @param a {物品体积，物品价值}
 * @return 能装入最大价值
 */
public int knapsack(int n, int[][] a) {
    int[][] dp = new int[a.length][n + 1];
    //初始化第一行
    for (int j = 0; j <= n; j++) {
        if (j < a[0][0]) {
            dp[0][j] = 0;
        } else {
            dp[0][j] = a[0][1];
        }
    }
    //填充其他行
    for (int i = 1; i < a.length; i++) {
        for (int j = 0; j <= n; j++) {
            if (j < a[i][0]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], a[i][1] + dp[i - 1][j - a[i][0]]);
            }
        }
    }
    //返回最后一个
    return dp[a.length - 1][n];
}

/**
 * @param n 背包容量
 * @param a {物品体积，物品价值}
 * @return 能装入最大价值
 */
public int knapsack2(int n, int[][] a) {
    int[] dp = new int[n + 1];
    //从后往前覆盖
    for (int i = 0; i < a.length; i++) {
        for (int j = n; j >= 0; j--) {
            if (j>=a[i][0]) {
                dp[j] = Math.max(dp[j], a[i][1] + dp[j - a[i][0]]);
            }
        }
    }
    //返回最后一个
    return dp[n];
}

/**
 * 检验能否分成两个等和子集：
 * 分割成两个等和子集,说明总和能被2整除，在此前提下，
 * 看其中的某些数字能否刚好组成一半的和 --> 0-1背包问题：背包容量：总和/2 , 物品体积和价值都为nums[i]
 * 取一半和作为背包容量，把数字放入背包，看背包能否放满
 * @param nums
 * @return
 */
public boolean canPartition(int[] nums) {
    int sum=0;
    for (int num : nums) {
        sum+=num;
    }
    if (sum%2!=0){
        return false;
    }
    int n=sum/2;
    int val=knapsack(n,nums);
    return n==val?true:false;//能否把背包放满
}

/**
 * 0-1背包问题
 * @param n
 * @param nums
 * @return
 */
private int knapsack(int n, int[] nums) {
    int[] dp=new int[n+1];
    for (int i = 0; i < nums.length; i++) {
        for (int j = n; j >=0 ; j--) {
            if (j>=nums[i]){
                dp[j]=Math.max(dp[j],nums[i]+dp[j-nums[i]]);
            }
        }
    }
    return dp[n];
}

/**
 * 把石头分成两份，求两份最小差值（最小差值为最后无法粉碎的最优值）
 * 每份石头都尽可能接近 总/2,差值最小 --> 0-1背包问题 --> 背包容量：总/2 , 物品体积和价值都为stones[i]
 * @param stones
 * @return
 */
public int lastStoneWeightII(int[] stones) {
    int sum=0;
    for (int stone : stones) {
        sum+=stone;
    }
    int maxVal=knapsack(sum/2,stones);
    return sum-maxVal*2;//两份差值
}

/**
 * 0-1背包
 * @param n
 * @param stones
 * @return
 */
private int knapsack(int n, int[] stones) {
    int[] dp=new int[n+1];
    for (int i = 0; i < stones.length; i++) {
        for (int j = n; j >=stones[i] ; j--) {
            dp[j]=Math.max(dp[j],stones[i]+dp[j-stones[i]]);
        }
    }
    return dp[n];
}