背包问题

1. 01背包

问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。注意：每件物品只能用一次，这就是01背包中01的含义 01背包用穷举法需要指数级别的时间复杂度，所以一般都用动态规划来解答我们这里只介绍一维滚动数组的解法，首先我们要确定dp数组的含义

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
递推公式：具体到某件物品，只有放入背包和不放入背包两种情况放入：dp[j] = dp[j - weight[i]] + value[i] 不放入：那就是自身，也就是dp[j] 那么递推公式就是这两种情况的最大值，即dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
初始化：关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
遍历顺序：这里有几种情况 4.1 先遍历物品，再遍历背包 4.2 先遍历背包，再遍历物品 4.3 遍历背包正序和倒序也有不同的含义（倒序遍历背包保证物品只遍历一次，正序每个物品就会遍历无数次，此时可以应用到完全背包）

        如果求组合数就是外层for循环遍历物品，内层for遍历背包。
        如果求排列数就是外层for遍历背包，内层for循环遍历物品

如果每个物品可以放入无数次，就演化成了完全背包问题接下来我们看几个例子

2. 分割等和子集

给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int x:nums) sum+=x;
        if(sum%2!=0) return false;
        int target = sum/2;
        /**
        dp[i][j] 代表背包容量为j时，从0-i个物品中取东西，能得到的最大价值，
        带入此题，背包的最大容量为target，
        物品便是从0-nums.length-1个物品中选取
        此题的背包最大容量为target，每个物品的价值为nums[i]
         */
       int[][] dp = new int[nums.length][target+1];
       for(int i=nums[0];i<=target;i++) dp[0][i] = nums[0];

       for(int i=1;i<nums.length;i++){
           for(int j=0;j<=target;j++){
                if (j >= nums[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
           }
       }
       return dp[nums.length-1][target]==target;
    }
}