数据结构与算法 / 系统课时
背包问题
背包问题
零一背包把“有限容量下如何选择物品”转化为标准动态规划模型。真正需要掌握的不只是转移公式,还包括二维状态的准确含义、一维压缩为何成立,以及容量必须倒序遍历的原因。
学习目标
- 能建立零一背包的二维状态并推导取或不取两类转移。
- 能把二维表压缩为一维数组,同时保持状态来源不被覆盖。
- 能根据物品使用次数判断容量应倒序还是正序遍历。
问题模型与二维状态
有 n 件物品,第 i 件物品的重量为 weights[i],价值为 values[i],背包容量为 C。每件物品最多选择一次,目标是在总重量不超过 C 的前提下获得最大价值。
定义 dp[i][c] 为“只考虑前 i 件物品、容量上限为 c 时能够获得的最大价值”。处理第 i 件物品时只有两类选择:不选择它,结果为 dp[i - 1][c];若容量足够,则选择它,结果为 dp[i - 1][c - w] + v。两者取最大值即可。
边界行 dp[0][c] 全为 0,表示没有物品时价值为 0。容量为 0 的列也为 0。二维表按物品行从上到下计算,每一行只依赖上一行。

从二维表压缩到一维数组
观察转移可以发现,第 i 行只读取第 i - 1 行,因此可以让一维数组 dp[c] 表示“处理完当前物品集合后,容量 c 的最大价值”。更新公式变为 dp[c] = max(dp[c], dp[c - w] + v)。
关键在于容量必须从 C 递减到 w。倒序时,读取的 dp[c - w] 还没有被当前物品更新,仍代表上一轮物品集合;若改为正序,较小容量会先写入当前物品的价值,后续较大容量又读取这个新值,相当于同一件物品被使用多次。
| 问题类型 | 单件物品可用次数 | 容量遍历方向 |
|---|---|---|
| 零一背包 | 最多一次 | 从大到小 |
| 完全背包 | 不限次数 | 从小到大 |
可运行示例
下面的程序分别实现二维和一维零一背包。示例中三件物品的重量为 2、3、4,价值为 4、5、10,容量为 6;最优方案选择重量 2 和 4 的两件物品,总价值为 14。
def knapsack_2d(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight = weights[i - 1]
value = values[i - 1]
for current_capacity in range(capacity + 1):
# 默认不选择当前物品,继承上一行结果。
dp[i][current_capacity] = dp[i - 1][current_capacity]
if current_capacity >= weight:
selected = dp[i - 1][current_capacity - weight] + value
dp[i][current_capacity] = max(
dp[i][current_capacity],
selected,
)
return dp
def knapsack_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for weight, value in zip(weights, values):
# 倒序保证每件物品在本轮最多使用一次。
for current_capacity in range(capacity, weight - 1, -1):
dp[current_capacity] = max(
dp[current_capacity],
dp[current_capacity - weight] + value,
)
return dp
if __name__ == "__main__":
item_weights = [2, 3, 4]
item_values = [4, 5, 10]
bag_capacity = 6
table = knapsack_2d(item_weights, item_values, bag_capacity)
compressed = knapsack_1d(item_weights, item_values, bag_capacity)
print("2D last row =", table[-1])
print("1D states =", compressed)
print("maximum value =", compressed[-1])预期输出
2D last row = [0, 0, 4, 5, 10, 10, 14]
1D states = [0, 0, 4, 5, 10, 10, 14]
maximum value = 14结果验证与复杂度
二维结果最后一行与一维数组完全一致,说明空间压缩没有改变状态语义。容量 6 的最优值为 14,对应重量 2 + 4;选择重量 3 + 4 会超过容量,因此价值 15 不可行。
二维实现需要填充 n × C 个状态,时间复杂度为 O(nC),空间复杂度为 O(nC)。一维实现仍执行相同数量级的转移,时间复杂度保持 O(nC),额外空间降为 O(C)。这里的复杂度依赖容量数值,因此属于伪多项式复杂度。
常见错误与边界
- 容量正序遍历:会让当前物品在同一轮被重复使用,把零一背包误写成完全背包。
- 重量与价值数组长度不一致:
zip会静默截断较长数组。工程代码应在计算前检查两者长度相等。 - 忘记容量下界:循环必须从
capacity到weight,否则访问dp[current_capacity - weight]时会使用负下标。 - 把“恰好装满”与“不超过容量”混淆:本课默认允许剩余空间,所以初始值全为
0;若要求恰好装满,需要用不可达标记区分尚未形成的容量状态。
本课练习
- 将示例改为容量
7,验证最优方案是否变为重量3 + 4、价值15,并输出一维数组的每轮状态。 - 在二维实现中增加选择路径回溯,输出被选物品的下标。验收条件是总重量不超过容量,且物品价值之和等于
dp[n][C]。
本课总结
- 二维状态
dp[i][c]表示前i件物品在容量c下的最大价值。 - 一维压缩成立的前提是转移只依赖上一行,倒序遍历用于保护上一轮状态。
- 零一背包与完全背包的核心差异体现在物品可用次数和容量遍历方向。
下一课预告
后续将继续学习更复杂的动态规划变体,例如完全背包、恰好装满和方案恢复,并练习根据约束变化重新定义状态与遍历顺序。