背包问题是动态规划中的经典问题类型，也是面试和竞赛中的高频考点。本文将系统讲解如何识别背包问题、通用的解题套路，并以 LeetCode 474「一和零」为例深入剖析。
一、如何识别背包问题
当你遇到以下特征的题目时，很可能是背包问题：
1.1 核心特征
问题描述中包含以下要素：
- 物品集合：有一组可选的物品（数组、列表等）
- 容量限制：存在一个或多个限制条件（重量、体积、数量等）
- 价值/目标：需要优化某个目标（最大价值、最小代价、方案数等）
- 选择约束：每个物品有选择次数的限制（选一次、无限次、至多 k 次等）
1.2 常见问法
背包问题通常以以下形式出现：
- “在限制 X 的情况下，最多/最少能…”
- “选择若干物品，使得总和不超过…”
- “有多少种方法可以…”
- “能否恰好达到…”
1.3 背包问题的分类
根据物品的选择规则和目标函数，背包问题分为：
| 类型 | 特点 | 典型问题 |
|---|---|---|
| 0-1 背包 | 每个物品只能选择 0 次或 1 次 | 「分割等和子集」 |
| 完全背包 | 每个物品可以选择无限次 | 「零钱兑换」 |
| 多重背包 | 每个物品可以选择有限次 | 「多重背包问题」 |
| 多维背包 | 有多个容量限制维度 | 「一和零」(本题) |
| 分组背包 | 物品分组，每组只能选一个 | 「分组背包问题」 |
二、背包问题的解题套路
2.1 解题五步法
Step 1: 确定状态定义
- 明确「物品」是什么
- 明确「容量」是什么
- 定义
dp[i][j]的含义：考虑前 i 个物品，容量为 j 时的最优解
Step 2: 确定状态转移方程
- 当前物品选还是不选？
- 选：
dp[i][j] = dp[i-1][j-cost] + value - 不选：
dp[i][j] = dp[i-1][j] - 取最优：
dp[i][j] = max/min(选, 不选)
Step 3: 确定初始状态
dp[0][0]表示什么？- 其他边界条件是什么？
Step 4: 确定遍历顺序
- 0-1 背包：物品在外层，容量倒序遍历（空间优化后）
- 完全背包：物品在外层，容量正序遍历
- 多维背包：嵌套多层循环
Step 5: 优化空间复杂度
- 二维 dp 通常可以优化为一维
- 注意遍历顺序的变化
2.2 代码模板
0-1 背包（二维）
// dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, capacity+1)
}
for i := 1; i <= n; i++ {
for j := 0; j <= capacity; j++ {
// 不选第 i 个物品
dp[i][j] = dp[i-1][j]
// 选第 i 个物品
if j >= weight[i-1] {
dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i-1]] + value[i-1])
}
}
}
0-1 背包（一维优化）
dp := make([]int, capacity+1)
for i := 0; i < n; i++ {
// 倒序遍历，避免重复使用
for j := capacity; j >= weight[i]; j-- {
dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
}
}
完全背包（一维）
dp := make([]int, capacity+1)
for i := 0; i < n; i++ {
// 正序遍历，允许重复使用
for j := weight[i]; j <= capacity; j++ {
dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
}
}
三、实战案例：LeetCode 474「一和零」
3.1 问题分析
题目描述：
给定一个二进制字符串数组 strs 和两个整数 m 和 n，找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1。
识别为背包问题：
- 物品集合：二进制字符串数组
strs - 容量限制：
m个 0 和n个 1（两个维度的限制） - 价值/目标：最大化选择的字符串数量
- 选择约束：每个字符串只能选一次
这是一个二维 0-1 背包问题！
3.2 解题思路
1. 状态定义
dp[i][j]：使用最多i个 0 和j个 1 时，能选择的最大字符串数量
2. 状态转移
对于每个字符串 str，统计其中 0 和 1 的个数 zeros 和 ones：
- 不选：
dp[i][j] = dp[i][j] - 选：
dp[i][j] = dp[i-zeros][j-ones] + 1 - 转移方程：
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)
3. 初始状态
dp[0][0] = 0：没有容量时，能选择 0 个字符串
4. 遍历顺序
- 外层遍历每个字符串
- 内层倒序遍历 m 和 n（0-1 背包特性）
3.3 代码实现
func findMaxForm(strs []string, m int, n int) int {
// dp[i][j] 表示使用 i 个 0 和 j 个 1 的最大字符串数量
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 遍历每个字符串
for _, str := range strs {
// 统计当前字符串的 0 和 1 的个数
zeros, ones := countZerosOnes(str)
// 倒序遍历容量（0-1 背包）
for i := m; i >= zeros; i-- {
for j := n; j >= ones; j-- {
// 选择当前字符串
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)
}
}
}
return dp[m][n]
}
// 统计字符串中 0 和 1 的个数
func countZerosOnes(s string) (int, int) {
zeros, ones := 0, 0
for _, ch := range s {
if ch == '0' {
zeros++
} else {
ones++
}
}
return zeros, ones
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
3.4 复杂度分析
-
时间复杂度：O(len(strs) × m × n)
- 外层遍历字符串数组：O(len(strs))
- 内层遍历二维容量：O(m × n)
- 统计每个字符串的 0 和 1：O(L)，其中 L 是字符串平均长度
- 总体：O(len(strs) × (L + m × n))
-
空间复杂度：O(m × n)
- dp 数组的大小
3.5 示例演示
以 strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 为例：
初始状态：dp[5][3] = 0
处理 "10" (zeros=1, ones=1):
dp[5][3] = max(0, dp[4][2] + 1) = 1
处理 "0001" (zeros=3, ones=1):
dp[5][3] = max(1, dp[2][2] + 1) = 2
处理 "111001" (zeros=2, ones=4):
跳过（ones > n）
处理 "1" (zeros=0, ones=1):
dp[5][3] = max(2, dp[5][2] + 1) = 3
处理 "0" (zeros=1, ones=0):
dp[5][3] = max(3, dp[4][3] + 1) = 4
最终答案：4
四、总结与扩展
4.1 关键要点
- 识别背包问题：物品 + 容量 + 目标优化
- 确定背包类型：0-1、完全、多重、多维
- 遵循解题套路：状态定义 → 转移方程 → 初始化 → 遍历顺序
- 注意空间优化：二维转一维，注意遍历顺序
4.2 相关题目推荐
多维背包问题：
- LeetCode 474「一和零」
- LeetCode 879「盈利计划」
0-1 背包变体：
- LeetCode 416「分割等和子集」
- LeetCode 494「目标和」
- LeetCode 1049「最后一块石头的重量 II」
完全背包变体：
- LeetCode 322「零钱兑换」
- LeetCode 518「零钱兑换 II」
- LeetCode 279「完全平方数」
4.3 进阶思考
- 如果要求输出具体的选择方案，如何修改代码？
- 如果物品数量达到 10^5 级别，如何优化？
- 能否使用贪心算法解决某些特殊的背包问题？
掌握背包问题的套路后，很多看似复杂的动态规划问题都能迎刃而解。多练习，多总结，你也能成为背包问题的高手！