先遍历物品还是先遍历背包二刷再考虑吧。累了，不想停留太久。

背包问题 二维 （卡码网题目）

各种解释：

要理解的是这个表格每一个格子都是当前所处情况的最大价值，我们用已经推导出的最大价值来推导当前情况的最大价值。

package DP;// i-1是指能选择的物品有i-1个而不一定真的放了i-1个物品
// dp【i】【j】 表示背包容量为 j 时，从 0..i 类物品种选取，可以获得的最大价值
// 如果有的朋友不理解对放物品i时为什么要是 j - weight【i】，这里可以理解为背包需要留出这个物品i的容量才可以放物品i
public class BagProblem {public static void main(String[] args) {int[] weight = {4,3,1};int[] value = {30,20,15};int bagSize = 4;testWeightBagProblem(weight,value,bagSize);}public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){int[][] dp = new int [weight.length][bagSize + 1];// 初始化dp数组/*** 初始化 dp 数组做了简化(给物品增加冗余维)。这样初始化dp数组，默认全为0即可。* dp[i][j] 表示从下标为[0 - i-1]的物品里任意取，放进容量为j的背包，价值总和最大是多少。* 其实是模仿背包重量从 0 开始，背包容量 j 为 0 的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。* 可选物品也可以从无开始，也就是没有物品可选，即dp[0][j]，这样无论背包容量为多少，背包价值总和一定为 0。* @param weight  物品的重量* @param value   物品的价值* @param bagSize 背包的容量*/// 创建数组后，其中默认的值就是0for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}// 填充 dp 数组for (int i = 1; i < weight.length; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]) { // 容量不够，放不进去dp[i][j] = dp[i - 1][j];} else { // 能放进去/*** 当前背包的容量可以放下物品i* 那么此时分两种情况：*    1、不放物品i*    2、放物品i* 比较这两种情况下，哪种背包中物品的最大价值最大*/dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);}// 打印dp数组（自己整个数组试试就知道了）System.out.println("i = " + i + "\t" + "j = " + j);for (int k = 0; k < weight.length; k++) {for (int z = 0; z <= bagSize; z++) {System.out.print(dp[k][z] + "\t");}System.out.println("\n");}}}}}

背包问题 一维（滚动数组） （卡码网题目，和上面那个题目是一样的）

难点在于，把二维数组变成了一维，相当于把上一行的数据复制到了下一行，不断滚动。最大的差异在于，遍历的顺序变成了从后往前，其实是没问题的，因为算本行数据只需要用到上一行的数据，本行前面的数据用不上，所以可以从后往前。倒序的时候左边元素再刷新前都是上一层的数据，但正序就不一样了，正序的时候，左边的元素刚刚刷新过，也就是左边的元素已经是本层的了，意味着什么 这样会导致一个物品反复加好几次。具体解释见下面截图：

难点：初始化也变了，因为从后往前遍历，所以可以内化到for循环里去。一维和二维的初始化其实是一个道理。你可以理解成二维数组初始化的时候，在物品0上面还有一个物品－1代表一个重量和价值都等于0的物体。 dp[j - weight[i]] 为什么不会越界？因为for循环里写了j > = weight[i] ！！！

for循环中途有一个条件不满足会直接退出，如下演示：

 public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen = weight.length;//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值int[] dp = new int[bagWeight + 1];//遍历顺序：先遍历物品，再遍历背包容量for (int i = 0; i < wLen; i++){for (int j = bagWeight; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}//打印dp数组for (int j = 0; j <= bagWeight; j++){System.out.print(dp[j] + " ");}}

416. 分割等和子集

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

难点：这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。就相当于，给你一个体积为sum/2的背包，让你挑选一种放东西的方法，使得放的东西最多，最多是多少，当然是放满，也就是sum/2，如果没放这么多，说明就是放不满，返回false。

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum += num;if (sum % 2 == 1) return false; // 和为奇数，不可等分int dp[] = new int [sum / 2 + 1];for (int i = 0; i < nums.length; i++) {for (int j = dp.length - 1; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[dp.length - 1] == sum / 2;}
}

public class Solution {public static void main(String[] args) {int num[] = {1,5,11,5};canPartition(num);}public static boolean canPartition(int[] nums) {int len = nums.length;// 题目已经说非空数组，可以不做非空判断int sum = 0;for (int num : nums) {sum += num;}// 特判：如果是奇数，就不符合要求if ((sum %2 ) != 0) {return false;}int target = sum / 2; //目标背包容量// 创建二维状态数组，行：物品索引，列：容量（包括 0）/*dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数每个数只能用一次，使得这些数的和恰好等于 j。*/boolean[][] dp = new boolean[len][target + 1];// 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满  （这里的dp[][]数组的含义就是“恰好”，所以就算容积比它大的也不要）if (nums[0] <= target) {dp[0][nums[0]] = true;}// 再填表格后面几行//外层遍历物品for (int i = 1; i < len; i++) {//内层遍历背包for (int j = 0; j <= target; j++) {// 直接从上一行先把结果抄下来，然后再修正dp[i][j] = dp[i - 1][j];//如果某个物品单独的重量恰好就等于背包的重量，那么也是满足dp数组的定义的if (nums[i] == j) {dp[i][j] = true;continue;}//如果某个物品的重量小于j，那就可以看该物品是否放入背包//dp[i - 1][j]表示该物品不放入背包，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；//dp[i - 1][j - nums[i]]表示该物品放入背包。如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。if (nums[i] < j) {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];}}}for (int i = 0; i < len; i++) {for (int j = 0; j <= target; j++) {System.out.print(dp[i][j]+" ");}System.out.println();}return dp[len - 1][target];}
}