背包 DP

动态规划 ⭐⭐ 中级 🔥 高频

💡 核心要点

背包问题的本质是：一组物品 + 容量限制 + 选择决策。掌握 0/1 背包和完全背包两个模板，理解遍历方向的原理，就能解决所有背包变体。

识别信号

看到以下特征时，优先考虑背包 DP：

• 给定一组"物品"（数字、字符串、物体），每个物品有某种"代价"或"重量"
• 存在一个"容量上限"或"目标值"（如背包容量、目标和、硬币总额）
• 需要从中选取若干个来满足某种条件（最优、计数、可行性）
• 题目中出现"恰好等于"、"不超过"、"凑成"、"装满"等字眼

常见变形信号：

信号词	可能的背包类型
每个元素只能用一次	0/1 背包
硬币/物品无限量	完全背包
每种物品有数量限制	多重背包
从若干组中各选一个	分组背包

通用思考框架

第一步：建立背包视角

拿到题目，先做一次"翻译"：

1. 物品是什么？ — 数组中的每个元素
2. 重量/代价是什么？ — 元素的值（或某种属性）
3. 背包容量是什么？ — 目标值、上限、约束
4. 问的是什么？ — 最大价值？方案数？能否恰好装满？

只要能完成这四步翻译，题目就变成了标准背包问题。

---

第二步：0/1 背包 vs 完全背包

这是最关键的区分：

• 每个物品最多用一次 → 0/1 背包
• 每个物品可以用无限次 → 完全背包

判断时问自己："同一个元素能重复选取吗？"

---

第三步：0/1 背包模板

二维 DP（直觉版）

定义状态：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 行只依赖第 i-1 行，可以压缩为一维。

一维 DP（滚动数组）

int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
    for (int j = capacity; j >= w[i]; j--) {  // 注意：倒序！
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

为什么必须倒序遍历容量？

这是 0/1 背包最容易犯错的地方，我们通过例子彻底讲清楚。

假设有一个物品，重量 w=2，价值 v=3，背包容量为 5。

当前 dp 数组（处理该物品前）：dp = [0, 0, 0, 0, 0, 0]

如果正序遍历（错误）：

j=2: dp[2] = max(dp[2], dp[0] + 3) = 3   → dp = [0, 0, 3, 0, 0, 0]
j=3: dp[3] = max(dp[3], dp[1] + 3) = 3   → dp = [0, 0, 3, 3, 0, 0]
j=4: dp[4] = max(dp[4], dp[2] + 3) = 6   ← 用了已经更新的 dp[2]！

dp[4] 计算时用到的 dp[2] 已经包含了这个物品（在 j=2 时更新过）， 相当于这个物品被使用了两次！这就变成了完全背包。

如果倒序遍历（正确）：

j=5: dp[5] = max(dp[5], dp[3] + 3) = 3   ← dp[3] 还未更新，来自上一轮
j=4: dp[4] = max(dp[4], dp[2] + 3) = 3   ← dp[2] 还未更新，来自上一轮
j=3: dp[3] = max(dp[3], dp[1] + 3) = 3
j=2: dp[2] = max(dp[2], dp[0] + 3) = 3

倒序时，dp[j-w[i]] 总是来自"还没处理当前物品"的状态，等价于二维 dp 中的 dp[i-1][j-w[i]]。

核心记忆法： 0/1 背包倒序 = 每个物品只用一次；完全背包正序 = 允许重复使用。

---

第四步：完全背包模板

与 0/1 背包唯一的区别：内层循环改为正序。

int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= capacity; j++) {  // 注意：正序！
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

为什么正序可以重复使用？

正序时，计算 dp[j] 用到的 dp[j-w[i]] 已经在本轮（处理当前物品时）被更新过， 即 dp[j-w[i]] 已经包含了当前物品，天然允许当前物品被再次选取。

---

第五步：三种问法的转移差异

同一个背包骨架，根据问题类型，转移方程和初始化都不同：

最优化问题（求最大/最小值）

// 求最大值
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
// 初始化：dp[0] = 0，其余可为 0（不要求装满）
//         或 dp[0] = 0，其余为 Integer.MIN_VALUE（要求恰好装满）

// 求最小值
dp[j] = Math.min(dp[j], dp[j - w[i]] + v[i]);
// 初始化：dp[0] = 0，其余为 Integer.MAX_VALUE（要求恰好装满时）

计数问题（求方案数）

dp[j] += dp[j - w[i]];
// 初始化：dp[0] = 1（空集是一种方案），其余为 0

可行性问题（能否恰好装满）

dp[j] = dp[j] || dp[j - w[i]];
// 初始化：dp[0] = true，其余为 false

三种问法的对应关系：

问法	转移操作	dp[0] 初始值	其他初始值
最大价值	max	0	0
最小代价（恰好装满）	min	0	MAX_VALUE
方案数	+=	1	0
可行性（能否装满）	||	true	false

---

第六步：多重背包 & 分组背包（进阶）

多重背包：每种物品有数量限制 c[i]

朴素做法是把每种物品展开为 c[i] 个独立物品，转化为 0/1 背包。 但这样复杂度高，可以用二进制拆分优化：

将数量 c 拆分为 1, 2, 4, ..., 2^k, c - (2^(k+1) - 1) 组， 每组作为一个"打包物品"，数量变为 O(log c)，显著降低复杂度。

分组背包：物品分为若干组，每组最多选一个

for (int g = 0; g < groups; g++) {         // 外层：枚举组
    for (int j = capacity; j >= 0; j--) {  // 中层：倒序容量（0/1 语义）
        for (int k : group[g]) {           // 内层：枚举组内物品
            if (j >= w[k])
                dp[j] = Math.max(dp[j], dp[j - w[k]] + v[k]);
        }
    }
}

注意循环顺序：组在最外层，容量在中间，组内物品在最内层。

---

典型例题：分割等和子集

LeetCode 416

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

为什么这是背包问题？

思维转化：两个子集和相等，意味着每个子集的和 = 总和 / 2。

问题变为：能否从数组中选出若干个数，使它们的和恰好等于 total / 2？

完成背包翻译：

• 物品：数组中的每个数
• 重量/代价：数字的值
• 背包容量：total / 2
• 问法：能否恰好装满？→ 可行性 0/1 背包

五步法解题

第一步：特判

总和为奇数时，无法平分，直接返回 false。 任何单个数大于 total / 2，也直接返回 false。

第二步：定义状态

dp[j] = 能否从数组中选出若干个数，使其和恰好为 j

第三步：初始化

dp[0] = true（和为 0，选空集，可行） 其余 dp[j] = false

第四步：转移方程

可行性 0/1 背包，倒序遍历：

dp[j] = dp[j] || dp[j - nums[i]]

第五步：返回结果

return dp[target]

Java 代码

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int num : nums) total += num;

    // 特判：总和为奇数
    if (total % 2 != 0) return false;

    int target = total / 2;

    // 特判：存在单个数大于 target
    for (int num : nums) {
        if (num > target) return false;
    }

    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // 空集，和为 0，可行

    for (int num : nums) {
        // 0/1 背包：倒序遍历，确保每个数只用一次
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

复杂度分析

• 时间复杂度：O(n × target)，其中 n 为数组长度，target = total / 2
• 空间复杂度：O(target)，一维滚动数组

---

延伸题目

题目	链接	与典型题的区别	关键技巧
目标和	LeetCode 494	0/1 背包计数变体	数学转换：sum(P) = (target + total) / 2，转为计数背包
零钱兑换	LeetCode 322	完全背包求最小值	初始化为 Integer.MAX_VALUE，转移前判断溢出
零钱兑换 II	LeetCode 518	完全背包计数	组合数：外层物品内层容量；排列数则反之（见 LC 377）
一和零	LeetCode 474	二维费用 0/1 背包	两个容量维度（0 的个数、1 的个数），都倒序遍历

目标和（LC 494）的关键推导：

设选"+"号的数之和为 P，选"-"号的数之和为 N，则：

• P + N = total
• P - N = target
• 解得：P = (total + target) / 2

问题转化为：从数组中选出若干个数，和恰好为 (total + target) / 2 的方案数。 这正是 0/1 背包计数问题，dp[j] += dp[j - num]，初始化 dp[0] = 1。

---

常见陷阱与调试

陷阱 1：0/1 背包误用正序遍历

症状：求最大价值时结果偏大，相当于每个物品被重复使用了。 检查：内层循环是否为 j = capacity; j >= w; j--。

陷阱 2：完全背包误用倒序遍历

症状：每种物品最多只用了一次，无法得到正确的最小硬币数。 检查：内层循环是否为 j = w; j <= capacity; j++。

陷阱 3：初始化错误

• 求最小值且要求恰好装满：除 dp[0] = 0 外其余应初始化为 Integer.MAX_VALUE，转移时需防止 MAX_VALUE + v 溢出（判断 dp[j-w] != Integer.MAX_VALUE）。
• 计数问题：dp[0] = 1，不是 0。
• 可行性问题：dp[0] = true，不是 false。

陷阱 4：整数溢出

零钱兑换等求最小值的题中，Integer.MAX_VALUE + 1 会溢出为负数：

if (dp[j - coin] != Integer.MAX_VALUE) {
    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}

陷阱 5：target 为负数或奇数时未特判

分割等和子集、目标和等题，计算 target 后需先检查合法性（非负、偶数要求等），否则数组越界或结果错误。

调试思路：

1. 用小规模例子手动推导 dp 数组的变化过程
2. 对比一维和二维 dp 的计算结果是否一致
3. 检查循环边界：外层是物品，内层是容量，方向是否正确
4. 检查初始化：dp[0] 的值是否符合"空集"的语义