30 秒速览
- 核心问题：给定容量，选物品使价值最大
- 分类：01 背包、完全背包、多重背包
- 状态定义：
dp[i][j]= 考虑前 i 个物品，容量 j 时的最大价值 - 空间优化：二维 → 一维（注意遍历顺序）
一、直觉建立
背包问题的本质
你有一个背包，容量有限。面前有一堆物品，每个物品有重量和价值。怎么选，才能在不超过容量的前提下，让价值最大？
背包容量：10
物品：
- A: 重量 3, 价值 4
- B: 重量 4, 价值 5
- C: 重量 5, 价值 6
最优解：选 A + C = 重量 8, 价值 10
三种背包类型
| 类型 | 特点 | 例子 |
|---|---|---|
| 01 背包 | 每个物品最多选 1 次 | 打包行李 |
| 完全背包 | 每个物品可以选无限次 | 找零钱 |
| 多重背包 | 每个物品有数量限制 | 买限量商品 |
二、01 背包
问题定义
有 n 个物品和一个容量为 W 的背包，每个物品只能用一次，求最大价值。
二维 DP
状态定义：
dp[i][j]= 考虑前 i 个物品，背包容量为 j 时的最大价值
转移方程：
对于第 i 个物品（重量 w[i]，价值 v[i]）：
- 不选：dp[i][j] = dp[i-1][j]
- 选（前提是 j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
代码实现：
def knapsack_01(W: int, weights: list[int], values: list[int]) -> int:
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i-1], values[i-1]
for j in range(W + 1):
# 不选第 i 个物品
dp[i][j] = dp[i-1][j]
# 选第 i 个物品
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
return dp[n][W]
复杂度：时间 O(nW)，空间 O(nW)
一维优化
观察到 dp[i][j] 只依赖 dp[i-1][...]，可以压缩成一维。
关键点：容量必须从大到小遍历，避免一个物品被选多次。
def knapsack_01_optimized(W: int, weights: list[int], values: list[int]) -> int:
dp = [0] * (W + 1)
for w, v in zip(weights, values):
# 从大到小遍历！
for j in range(W, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[W]
为什么从大到小？
假设 W = 10, w = 3
从大到小：dp[10] 用的是 dp[7]，dp[7] 用的是 dp[4]，dp[4] 用的是 dp[1]
→ 每个容量只用上一轮的值，物品只选一次
从小到大：dp[1] 更新后，dp[4] 会用新的 dp[1]，dp[7] 会用新的 dp[4]
→ 同一物品可能被选多次，变成完全背包！
复杂度：时间 O(nW)，空间 O(W)
三、完全背包
问题定义
每种物品可以选无限次。
转移方程
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
↑ ↑
不选第 i 个 选第 i 个（还能继续选）
注意：选第 i 个时，用 dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]，因为选了还能再选。
一维实现
关键点：容量从小到大遍历，因为物品可以选多次。
def knapsack_complete(W: int, weights: list[int], values: list[int]) -> int:
dp = [0] * (W + 1)
for w, v in zip(weights, values):
# 从小到大遍历！
for j in range(w, W + 1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[W]
01 背包 vs 完全背包
| 类型 | 遍历顺序 | 原因 |
|---|---|---|
| 01 背包 | 容量从大到小 | 每个物品只能选一次 |
| 完全背包 | 容量从小到大 | 每个物品可以选多次 |
四、典型例题
例题 1：LC 416. 分割等和子集
题目：给定一个只包含正整数的数组，判断能否分成两个和相等的子集。
示例：
输入：nums = [1,5,11,5]
输出：true（[1,5,5] 和 [11]，和都是 11）
思路
转化为 01 背包问题：
- 背包容量 = sum / 2
- 物品 = 数组元素
- 目标 = 恰好装满
def canPartition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
# 从大到小，01 背包
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]
复杂度：时间 O(n × sum)，空间 O(sum)
例题 2：LC 494. 目标和
题目：给数组每个元素前加 + 或 -，使结果等于 target，求方案数。
示例：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：有 5 种方法得到 3
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
...
思路
设 P 为正数和，N 为负数和：
- P + N = sum
- P - N = target
- P = (sum + target) / 2
转化为：从数组中选若干数，使其和等于 P。
def findTargetSumWays(nums: list[int], target: int) -> int:
total = sum(nums)
# (sum + target) 必须是偶数且非负
if (total + target) % 2 != 0 or total + target < 0:
return 0
bag_size = (total + target) // 2
# dp[j] = 填满容量 j 的方案数
dp = [0] * (bag_size + 1)
dp[0] = 1
for num in nums:
for j in range(bag_size, num - 1, -1):
dp[j] += dp[j - num]
return dp[bag_size]
复杂度：时间 O(n × sum)，空间 O(sum)
例题 3：LC 322. 零钱兑换
题目：给定硬币面额和目标金额，求凑成金额的最少硬币数。
示例：
输入：coins = [1,2,5], amount = 11
输出：3（5+5+1）
思路
完全背包问题（硬币可重复使用），求最小值。
def coinChange(coins: list[int], amount: int) -> int:
# dp[j] = 凑成金额 j 的最少硬币数
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
# 从小到大，完全背包
for j in range(coin, amount + 1):
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
复杂度：时间 O(amount × n)，空间 O(amount)
例题 4：LC 518. 零钱兑换 II
题目：给定硬币面额和目标金额，求凑成金额的方案数。
示例：
输入：amount = 5, coins = [1,2,5]
输出：4
解释：4 种方式
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
思路
完全背包，求方案数。
def change(amount: int, coins: list[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[amount]
组合 vs 排列：
- 组合（顺序无关）：外层遍历物品，内层遍历容量
- 排列（顺序有关）：外层遍历容量，内层遍历物品
# 求排列数（如 LC 377）
def combinationSum4(nums: list[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
# 外层遍历容量
for j in range(1, target + 1):
# 内层遍历物品
for num in nums:
if j >= num:
dp[j] += dp[j - num]
return dp[target]
例题 5：LC 1049. 最后一块石头的重量 II
题目：每次选两块石头相撞，差值作为新石头，求最后剩下的最小重量。
思路
转化为：把石头分成两堆，使两堆重量差最小。 即：选一些石头，使其和尽可能接近 sum/2。
def lastStoneWeightII(stones: list[int]) -> int:
total = sum(stones)
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for stone in stones:
for j in range(target, stone - 1, -1):
dp[j] = dp[j] or dp[j - stone]
# 找最大的可达重量
for j in range(target, -1, -1):
if dp[j]:
return total - 2 * j
return total
五、背包问题总结
遍历顺序速查
| 问题类型 | 物品遍历 | 容量遍历 |
|---|---|---|
| 01 背包求最值 | 外层 | 从大到小 |
| 01 背包求方案数 | 外层 | 从大到小 |
| 完全背包求最值 | 外层 | 从小到大 |
| 完全背包求组合数 | 外层 | 从小到大 |
| 完全背包求排列数 | 内层 | 从小到大 |
状态初始化
# 求最大价值
dp = [0] * (W + 1)
# 求最小数量
dp = [float('inf')] * (W + 1)
dp[0] = 0
# 求方案数
dp = [0] * (W + 1)
dp[0] = 1
# 求是否可行
dp = [False] * (W + 1)
dp[0] = True
六、常见错误与陷阱
错误 1：遍历顺序错误
# 01 背包错误：从小到大
for j in range(w, W + 1): # 物品会被选多次
dp[j] = max(dp[j], dp[j - w] + v)
# 正确：从大到小
for j in range(W, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
错误 2：求方案数时初始化错误
# 错误：dp[0] = 0
dp = [0] * (target + 1)
# 正确：dp[0] = 1（容量为 0 有 1 种方案：什么都不选）
dp = [0] * (target + 1)
dp[0] = 1
错误 3：组合 vs 排列混淆
# 组合（顺序无关）：1+2 和 2+1 算一种
# 外层物品，内层容量
# 排列（顺序有关）：1+2 和 2+1 算两种
# 外层容量，内层物品
七、复盘清单
触发信号
- 选/不选问题
- 容量限制
- 求最值/方案数/可行性
- 物品可重复/不可重复
类型判断
- 物品只能选一次 → 01 背包
- 物品可以选多次 → 完全背包
- 顺序重要 → 排列（外层容量）
- 顺序不重要 → 组合（外层物品）
实现检查
- 遍历顺序正确
- 初始化正确
- 边界条件处理
八、题目清单
01 背包
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 416 | 分割等和子集 | Medium | 判断可行性 |
| 494 | 目标和 | Medium | 方案数 |
| 1049 | 最后一块石头 II | Medium | 最小差值 |
完全背包
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 322 | 零钱兑换 | Medium | 最少数量 |
| 518 | 零钱兑换 II | Medium | 组合数 |
| 377 | 组合总和 IV | Medium | 排列数 |
| 279 | 完全平方数 | Medium | 最少数量 |