背包理论基础
掌握01背包，和完全背包，足够应付大厂面试。
01 背包二维
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
1.确定dp数组以及下标的含义：
对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.确定递推公式
有两个方向推出来dp[i][j]，
-
不放物品i：由
dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。) -
放物品i：由
dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]]+ value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.dp数组如何初始化
4.确定遍历顺序：先物品，后背包。二维来说其实都行。
01 背包一维（滚动数组）
如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
1.确定dp数组的定义：在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2.dp数组的递推公式
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）
此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
3.一维dp数组如何初始化
看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
4.一维dp数组遍历顺序：倒序遍历，保证同一件物品不会被重复添加。先遍历物品嵌套遍历背包容量。
如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品，而不会循环更新。
416. 分割等和子集
题目链接/文字讲解：分割等和子集
题设：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：动规五部曲：
1.确定dp数组以及下标的含义01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。
本题中每一个元素的数值既是重量，也是价值。
2.确定递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.dp数组如何初始化：只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
4.确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
class Solution {
public boolean canPartition(int[] nums) {
Arrays.stream(nums).sorted();
int sum = Arrays.stream(nums).sum();
if (sum % 2 == 1) return false;
int targetSum = sum / 2;
int[] dp = new int[targetSum + 1];
//dp[j]代表大小为j的数组能放入的最大容量
for (int i = 0; i < nums.length; i++) {
for (int j = targetSum; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[targetSum] == targetSum) return true;
return false;
}
}
