01 背包
假设有音响、电脑、吉他 3 个物品，它们的重量分别是 4、3、1，它们的价值分别是 3000、2000、1500，现在有个容量为 4 的背包，问如何拿取才能使价值最大。（题目来源：算法图解）
背包问题的本质可以理解为 “约束” 和 “价值” 的权衡，在一定的 “约束” 下完成 “价值” 的最大化。
本题本质上就是一个决策题，所以可以用回溯的方法暴力求解，每个物品都有选和不选两种选择，所以时间复杂度是 O(2^n)，比较耗时。
本题可以使用动态规划来解决，动态规划的核心思想之一就是先解决子问题，然后再逐步解决大问题，因此往往需要一个表格来记录小问题的解，具体是一维表格还是二维表格待定。
整体问题是从 m 个物品中选，如何选，使的在容量限制为 n 的情况下价值最大。我们再来思考一下什么是子问题，这里我们使用 “二极管” 法思考，假如我们先在前 m - 1 个物品中做选择，并且确定了在 n 的限制下的最大价值，我们记为 A，那么对于第 m 个物品，我们有几种决策呢？三种！
一是第 m 个物品超重了，背包装不下，那就不选了，于是最大价值就是 A。
二是第 m 个物品没超重，背包还能装，但是不装，那么最大价值还是 A。
三是第 m 个物品没超重，背包还能装，但是装了，那么最大价值有可能是当前物品的价值 + 剩余容量所能承载的最大价值，也可能仍然是 A，我们要取二者中的最大的。
注意前面提到的 m - 1 是指我们假设只在前 m - 1 个物品中做选择，没考虑第 m 个物品，当我们考虑第 m 个物品并把它纳入选择的时候，前 m - 1 个物品还没选，为什么呢，因为每纳入一件新物品我们都要重新选择，毕竟之前做的选择在纳入新物品后其价值不一定是最大的了。这就解释了为什么在选择第 m 个物品后还要知道 剩余容量所能承载的最大价值，因为其他 m - 1 个物品还没选。从这里还可以看出，我们除了关注某个物品，还需要考虑 容量 这个变量。因此我们的表格应该是二维的，表格中的行表示的是物品，列表示的是从 0 到 n 的容量。
按照这个 “二极管” 法思考，我们就能一步步的往前推，就能明确表格（dp 数组）的含义：dp[i][j]，它表示背包容量为 j 的限制下，在 0 ~ i 中选择物品，得到的最大价值；也能得到状态转移方程：
dp[i][j] = dp[i - 1][j];超重dp[i][j] = Math.max(dp[i - 1][j], values[i] + dp[i - 1][j - weights[i]]);不超重，在选择和不选择第 i 个物品中，挑价值最大的
dp[i - 1][j] 表示的是在背包容量为 j 的情况下，在前 0 ~ i - 1 个物品中做选择，所能达到的最大价值。
values[i] 表示当前物品的价值，weights[i] 表示当前物品的重量。
dp[i - 1][j - weights[i]] 表示在背包容量为 j 的情况下，选了第 i 个物品后，剩余容量所能承载的最大价值，i - 1 是因为第 i 个物品已经选了，该去剩下的 0 ~ i - 1 个物品中去做选择。
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 物品的数量
int m = sc.nextInt();
// 背包的容量
int n = sc.nextInt();
// 物品重量数组
int[] spaces = new int[m];
// 物品价值数组
int[] values = new int[m];
for (int i = 0; i < m; i++) {
spaces[i] = sc.nextInt();
}
for (int i = 0; i < m; i++) {
values[i] = sc.nextInt();
}
// backtrace(spaces, values, m, n, 0, 0);
int max = dpSolution(spaces, values, m, n);
System.out.println(max);
sc.close();
}
// 暴力回溯
public static int maxValue = 0;
public static void backtrace(int[] spaces, int[] values, int m, int n, int idx, int val) {
if (idx == m || n == 0) {
maxValue = Math.max(maxValue, val);
return;
}
for (int i = idx; i < m; i++) {
if (n - spaces[i] >= 0) {
backtrace(spaces, values, m, n - spaces[i], i + 1, val + values[i]);
}
}
}
// 动态规划
public static int dpSolution(int[] spaces, int[] values, int m, int n) {
// dp[i][j] 表示从 0 ~ i 个物品中选择，在背包容量为 j 时的最大价值
int[][] dp = new int[m][n + 1];
// 递推公式，dp[i][j]，容量为 j 时，
// 在当前物品可选的情况下的价值（当前物品的价值和剩余容量的最大价值）v[i] + dp[i-1][j-当前物品的重量] (dp[i-1[j-w[i]])
// 和
// 当前物品不可选的情况下的价值，即 dp[i-1][j]
// 谁更大。
// 初始化，根据递推公式可知，我们要往左上角查找，所以要把第一列和第一行初始化
// 初始化第一列为 0，默认都是 0
// 初始化第一行
for (int j = 0; j < dp[0].length; j++) {
// 第一行只能选第一个物品
if (spaces[0] <= j) {
dp[0][j] = values[0];
}
}
// 遍历，按行遍历，从小背包开始，用小问题的解解决大问题
for (int i = 1; i < m; i++) {
for (int j = 1; j <= n; j++) {
if (spaces[i] <= j) {
// 放得下 i，但要考虑放与不放哪个价值大
dp[i][j] = Math.max(dp[i - 1][j], values[i] + dp[i - 1][j - spaces[i]]);
} else {
// 放不下
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m - 1][n];
}
}
416. 分割等和子集
其实就是从集合中选择一个值放入左边口袋，剩下的在右边口袋，问能否使两个口袋的和相等。是一个决策问题，可以试下回溯算法。
这里对和的计算使用了巧妙的方法，左边口袋的和就是从 0 开始增加，右边口袋的和就是从原数组之和开始减少。
function canPartition(nums: number[]): boolean {
const rightSum = nums.reduce((currSum, curr) => currSum + curr, 0);
return backtrace(nums, 0, 0, rightSum);
}
function backtrace(nums: number[], idx: number, leftSum: number, rightSum: number) {
if (idx === nums.length) return false;
if (leftSum === rightSum) return true;
for (let i = idx; i < nums.length; i++) {
leftSum += nums[i];
rightSum -= nums[i];
const can = backtrace(nums, i + 1, leftSum, rightSum);
// 有一个结果为 true，就将答案逐级向上返回
if (can) return true;
leftSum -= nums[i];
rightSum += nums[i];
}
return false;
}哈哈，看了题解才发现，题目还有隐含的另一个信息。一个集合，分成两部分，这两部分的和还相等，那么每部分的和就是原集合的和（sum）除以 2。如果题目推广到原集合分为 k 个和相等的小集合，那么小集合的和就是 sum / k，参考 698. 划分为k个相等的子集。
所以如果原数组长度小于 2，那就无解，如果 sum / 2 不是整数的话，那也无解。如果某个值大于 sum / 2 的话还是无解。经过这三个判断后再开始遍历，如果有和等于 sum / 2，那说明这就是个解，剩下的值的和肯定也是 sum / 2。
其实这个题可以抽象为 01 背包问题，集合里面的数要么选，要么不选，选几个数使其填满容量为 sum / 2 的背包。dp[i][j] 定义为在 0 ~ i 中选择几个数字，其和能否等于 j。如果数字 i 大于 j 的话，那就不能选择，dp[i][j] 就等于 dp[i - 1][j]；否则可选可不选，但无论选择与否，只要 dp[i - 1][j] 和 dp[i - 1][j - nums[i]] 有一个为 true，dp[i][j] 都为 true。
class Solution {
public boolean canPartition(int[] nums) {
if (nums.length < 2) return false;
int sum = 0;
int max = 0;
for (int item: nums) {
sum += item;
if (item > max) {
max = item;
}
}
if (sum % 2 != 0) return false;
// 如果有大于 target 的数，那么一定无法平等划分子集
int target = sum / 2;
if (max > target) return false;
int len = nums.length;
boolean[][] dp = new boolean[len][target + 1];
for (int i = 0; i < len; i++) {
dp[i][0] = false;
}
// 当 i == 0 时，只有 nums[0] 是可选的，因此 dp[0][nums[0]] = true
// nums 中的数都是小于等于 target 的
dp[0][nums[0]] = true;
for (int i = 1; i < len; i++) {
for (int j = 1; j <= target; j++) {
if (nums[i] <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[len - 1][target];
}
}