1. 概述
背包问题是一个历史悠久且广泛应用的优化问题。在本教程中，我们会介绍背包问题的几个变种，并重点讨论 0-1 背包问题。
我们还会解释为什么 0-1 背包问题是 NP-Complete 的，以及如何使用 动态规划算法 在 伪多项式时间 内求解它。
2. 问题定义
给定一个最大承重为 W 的背包，以及一组物品，每个物品都有自己的重量 w[i] 和价值 v[i]。我们的目标是：
在不超过背包承重的前提下，选取物品使得总价值最大。
这是一个典型的优化问题，数学表达如下：
- 目标函数：
max Σ(v[i] * x[i])，其中x[i] ∈ {0, 1} - 约束条件：
Σ(w[i] * x[i]) ≤ W
3. 背包问题的变种
根据物品是否可以重复选取，背包问题有以下三种变种：
3.1 0-1 背包问题（0-1 Knapsack）
每个物品只能选一次或不选：
x[i] ∈ {0, 1}
这是最基础也是最经典的形式，本教程将重点讲解。
3.2 有界背包问题（Bounded Knapsack）
每个物品最多可以选 c 次：
0 ≤ x[i] ≤ c
适用于有限库存的场景。
3.3 无界背包问题（Unbounded Knapsack）
每个物品可以无限次选取：
x[i] ≥ 0
适用于物品无限供应的情况。
4. 为什么 0-1 背包问题是 NP-Complete？
判断版本的 0-1 背包问题属于 NP-Complete 类：
给定物品的重量和价值，是否存在一个子集，使得总重量不超过
W且总价值至少为V？
这个问题可以归约到经典的 子集和问题（Subset Sum Problem），而子集和问题是已知的 NP-Complete 问题。
因此，0-1 背包问题也是 NP-Complete 的。
不过，它可以在 伪多项式时间 内求解，因为其复杂度与 W 的数值大小相关，而不是其二进制位数。
5. 动态规划解法（DP）
我们使用一个二维数组 dp[i][w] 表示前 i 个物品、总重量不超过 w 时的最大价值。
状态转移方程：
if w[i] > w:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])
初始化：
dp[0][w] = 0（没有物品，价值为 0）dp[i][0] = 0（容量为 0，无法装物品）
时间复杂度：
✅ O(n * W)
⚠️ 注意：W 是重量上限，不是输入长度的函数，因此该算法属于 伪多项式时间。
6. 示例演示
我们有如下物品：
| 物品编号 | 重量 | 价值 |
|---|---|---|
| 1 | 1 | 10 |
| 2 | 2 | 40 |
| 3 | 1 | 20 |
| 4 | 3 | 20 |
| 5 | 5 | 60 |
背包最大承重为 W = 10。
我们使用动态规划构造如下 DP 表格：
weight → 0 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------------
物品0 0 0 0 0 0 0 0 0 0 0 0
物品1(1,10) 0 10 10 10 10 10 10 10 10 10 10
物品2(2,40) 0 10 40 50 50 50 50 50 50 50 50
物品3(1,20) 0 20 40 60 70 70 70 70 70 70 70
物品4(3,20) 0 20 40 60 70 70 80 90 90 90 90
物品5(5,60) 0 20 40 60 70 70 80 100 120 130 130
最终结果：
✅ 最大价值为 130，当背包承重为 10 时。
7. 时间复杂度分析
- 初始化：
O(n + W) - 两层循环：
O(n * W) - 每次状态转移：
O(1)
✅ 总时间复杂度为 O(nW)
⚠️ 注意：虽然看起来是多项式时间，但 W 是数值大小，不是输入长度的函数。因此它是 伪多项式时间。
例如，当 W 从 100 增加到 1000，虽然数值只增加了 10 倍，但二进制表示从 7 位增加到 10 位，处理时间呈指数增长。
8. 总结
- 0-1 背包问题是经典的 NP-Complete 问题。
- 可以使用 动态规划 在
O(nW)时间内求解。 - 由于复杂度依赖于数值大小，因此属于 伪多项式时间算法。
- 适用于物品数量不大、重量上限适中的场景。
💡 踩坑提示：
- 不要使用递归暴力解法，会超时。
- 优化空间复杂度时可使用滚动数组。
- 注意初始化边界条件，否则容易出错。