背包问题（01背包+leetcode416）

动态规划合集：

1.矩阵链乘法
2.投资组合问题
3.完全背包问题
4.01背包问题
5.最长公共子序列

例题4——01背包

题目描述（Leetcode 416）

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

解题分析

能否将数组分成两部分，且两部分彼此相等。

首先就是将元素都加起来，因为都是正整数，如果和为奇数，那么分成两部分怎么分两部分也不可能相等。

如果总和为偶数，那么问题就转变成 从数组中，挑出来相加等于总和一半的数，如果挑不出来那就是不存在，否则就是存在。（从一堆物品中挑出来装入背包，背包的总重为 总和的一半 ）

建模：

表示选前k个数，且总和不超过y时可以加出来的和。那么也就是可以凑出来值为target的组合。若不等，则不存在。

题解

public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n <= 0) return false;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum %2 == 1){
            return false;
        }
        int target = sum >> 1;
        int [][]dp = new  int[n+1][target+1];
        //
        int y = target;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <=  target; j++) {
                int left = dp[i-1][j];
                int right;
                if (j-nums[i-1] < 0){
                    right = Integer.MIN_VALUE;
                }
                else {
                    right = dp[i-1][j-nums[i-1]]+nums[i-1];
                }
                dp[i][j] = Math.max(left,right);
            }
        }
        if (dp[n][target] == target)
            return true;
        return false;
    }

大神解法

public boolean canPartition(int[] nums) {
    int sum = 0;

    for (int num : nums) {
        sum += num;
    }

    if ((sum & 1) == 1) {
        return false;
    }
    sum /= 2;

    int n = nums.length;
    boolean[] dp = new boolean[sum+1];
    Arrays.fill(dp, false);
    dp[0] = true;

    for (int num : nums) {
        for (int i = sum; i > 0; i--) {
            if (i >= num) {
                dp[i] = dp[i] || dp[i-num];
            }
        }
    }
    return dp[sum];
}

先说优点，再说其思路。

代码优点：for的迭代器写法，位操作判断奇偶，备忘录用二进制（节省存储还好用）

思路：只维护一个一维矩阵，长度为target+1

递推公式为：

表示，使用前k个数，能否凑出和为y。能则为true，不能则为false。子问题还是考y,k来界定的。

表示使用所有的数，能否凑出和为target。若能则返回true，否则false。