数据结构与算法 / 系统课时
建立零一背包的容量状态
建立零一背包的容量状态
零一背包要解决的核心问题是:每件物品只能选一次,在容量有限时如何取得最大价值。关键不在“背包”这个故事,而在于把“处理到第几件物品”和“当前可用容量”建成状态,再看清一维压缩后状态的读取方向。
学习目标
- 用物品阶段与容量定义零一背包状态,并写出转移方程
- 理解二维 DP 如何压缩成一维容量数组
- 解释容量为什么必须逆序遍历,避免同一物品被重复使用
从二维状态开始建模
设有 n 件物品,第 i 件物品重量为 w[i]、价值为 v[i],背包容量为 C。最直接的状态是:
( dp[i][c] )
它表示只考虑前 i 件物品、容量上限为 c 时能取得的最大价值。处理第 i 件物品时只有两种选择:不选它,沿用上一阶段结果;或者在容量足够时选它,再加上剩余容量对应的上一阶段结果。
这里两个候选值都来自 i-1 层,这正是“每件物品最多使用一次”的数学约束。

压缩为一维容量数组
因为第 i 层只依赖第 i-1 层,可以去掉物品维度,只保留 dp[c]。此时 dp[c] 表示处理完当前已遍历物品后,容量 c 能获得的最大价值。
主示例使用三件物品:重量分别为 2、3、4,价值分别为 4、5、7,背包容量为 5。
def zero_one_knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# 逆序保证 dp[c - w] 仍来自“使用当前物品之前”的状态
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
weights = [2, 3, 4]
values = [4, 5, 7]
print(zero_one_knapsack(weights, values, 5))预期输出
9容量为 5 时,最优方案是选择重量 2 和 3 的两件物品,价值为 4 + 5 = 9。
为什么容量必须逆序
假设当前物品重量为 2、价值为 4。如果容量正序遍历,先更新 dp[2] = 4,接着计算 dp[4] 时就可能读取刚刚更新过的 dp[2],得到 dp[4] = dp[2] + 4 = 8。这等价于同一件物品在同一轮被用了两次。
逆序时先计算大容量。计算 dp[4] 所读取的 dp[2] 仍是本轮处理当前物品之前的旧值,因此当前物品最多只会贡献一次。
复杂度与状态含义
二维写法的时间复杂度是 ,空间复杂度是 ;压缩为一维后,时间复杂度不变,空间复杂度降为 。
一维优化改变的是存储方式,不是状态语义。dp[c] 依然表示在当前已处理物品集合下,容量 c 的最优价值。逆序遍历则负责维持原来“只从上一层读取”的逻辑边界。
只要题目同时具备“每个对象最多使用一次”和“总资源不能超过上限”这两个特征,就应优先尝试零一背包模型;一维优化时,再用逆序遍历守住一次性选择的约束。