数据结构与算法 / 系统课时

建立零一背包的容量状态

建立零一背包的容量状态

零一背包要解决的核心问题是:每件物品只能选一次,在容量有限时如何取得最大价值。关键不在“背包”这个故事,而在于把“处理到第几件物品”和“当前可用容量”建成状态,再看清一维压缩后状态的读取方向。

学习目标

  • 用物品阶段与容量定义零一背包状态,并写出转移方程
  • 理解二维 DP 如何压缩成一维容量数组
  • 解释容量为什么必须逆序遍历,避免同一物品被重复使用

从二维状态开始建模

设有 n 件物品,第 i 件物品重量为 w[i]、价值为 v[i],背包容量为 C。最直接的状态是:

( dp[i][c] )

它表示只考虑前 i 件物品、容量上限为 c 时能取得的最大价值。处理第 i 件物品时只有两种选择:不选它,沿用上一阶段结果;或者在容量足够时选它,再加上剩余容量对应的上一阶段结果。

dp[i][c]=max⁡(dp[i−1][c], dp[i−1][c−wi]+vi)dp[i][c] = \max(dp[i-1][c],\ dp[i-1][c-w_i] + v_i)

这里两个候选值都来自 i-1 层,这正是“每件物品最多使用一次”的数学约束。

零一背包二维状态到一维状态的依赖关系

压缩为一维容量数组

因为第 i 层只依赖第 i-1 层,可以去掉物品维度,只保留 dp[c]。此时 dp[c] 表示处理完当前已遍历物品后,容量 c 能获得的最大价值。

主示例使用三件物品:重量分别为 2、3、4,价值分别为 4、5、7,背包容量为 5。

python
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))

预期输出

text
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] 仍是本轮处理当前物品之前的旧值,因此当前物品最多只会贡献一次。

复杂度与状态含义

二维写法的时间复杂度是 O(nC)O(nC),空间复杂度是 O(nC)O(nC);压缩为一维后,时间复杂度不变,空间复杂度降为 O(C)O(C)。

一维优化改变的是存储方式,不是状态语义。dp[c] 依然表示在当前已处理物品集合下,容量 c 的最优价值。逆序遍历则负责维持原来“只从上一层读取”的逻辑边界。

只要题目同时具备“每个对象最多使用一次”和“总资源不能超过上限”这两个特征,就应优先尝试零一背包模型;一维优化时,再用逆序遍历守住一次性选择的约束。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

建立零一背包的容量状态

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通