graph LR A[背包] --> B[01背包] A --> C[完全背包] A --> D[多重背包] B --> E[逆序枚举] C --> F[正序枚举]
背包问题是动态规划中最经典的模型族，面试中出现频率极高。核心形式：
有 n 个物品和一个容量为 W 的背包，每个物品有重量 w[i] 和价值 v[i]，如何选择物品使总价值最大？
| 类型 | 每个物品可选次数 | 典型题 |
|---|---|---|
| 0/1 背包 | 0 或 1 | 分割等和子集 |
| 完全背包 | 无限次 | 零钱兑换 |
| 多重背包 | 有限次 | 限定数量的组合 |
| 分组背包 | 每组选一个 | 课程选择 |
dp[i][j] = 考虑前 i 个物品、背包容量为 j 时的最大价值。
dp[i][j] = max(
dp[i-1][j], // 不选第 i 个
dp[i-1][j-w[i]] + v[i] // 选第 i 个（前提：j >= w[i]）
)
交互式动画演示，可调整参数并单步执行。
全屏打开| i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 物1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 物2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 物3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
public int knapsack01(int[] weights, int[] values, int W) {
int n = weights.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][W];
}public int knapsack01(int[] weights, int[] values, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < weights.length; i++) {
for (int j = W; j >= weights[i]; j--) { // 逆序！
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}关键：0/1 背包一维优化必须逆序遍历容量，保证每个物品只用一次。
每个物品可以选无限次。
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
public int knapsackComplete(int[] weights, int[] values, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < weights.length; i++) {
for (int j = weights[i]; j <= W; j++) { // 正序！
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}关键：完全背包一维优化必须正序遍历容量，允许同一物品重复使用。
| 类型 | 外层 | 内层 | 原因 |
|---|---|---|---|
| 0/1 背包 | 物品 | 容量逆序 | 防止同一物品重复选 |
| 完全背包 | 物品 | 容量正序 | 允许重复选 |
问题：数组能否分成两个等和子集？→ 能否凑出 sum/2。
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}问题：最少硬币数凑出金额。
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}问题：凑出金额的组合数（不计顺序）。
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) { // 外层物品 → 组合（非排列）
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}组合 vs 排列：外层遍历物品 = 组合；外层遍历容量 = 排列。
问题：给数组元素添加 +/- 使和为 target 的方案数。
转化为：选一部分数使其和 = (sum + target) / 2 → 0/1 背包计数。
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
if ((sum + target) % 2 != 0 || Math.abs(target) > sum) return 0;
int bag = (sum + target) / 2;
int[] dp = new int[bag + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = bag; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[bag];
}每个物品最多选 s[i] 次。
| 信号 | 对应类型 |
|---|---|
| "每个元素用一次" | 0/1 背包 |
| "可以重复使用" | 完全背包 |
| "能否恰好凑出" | 可行性背包（boolean） |
| "方案数" | 计数背包（累加） |
| "最大/最小价值" | 最优背包（max/min） |
dp[0]=1；求最值 dp[0]=0，其余为 INF 或 -INF。