0/1 背包问题

给定 $n$ 件物品，每件物品有非负整数重量 $w_i$ 和价值 $v_i$。在背包容量 $C$ 的限制下，每件物品最多选一次，求最大总价值：

$$\max \sum_i v_i x_i \quad\text{s.t.}\quad \sum_i w_i x_i \le C,\qquad x_i\in\{0,1\}.$$

状态定义与转移

定义 dp[c] 为容量为 c 时能装下的最大价值。

核心技巧在于一维数组的逆序更新。遍历每件物品时，从大到小更新容量：

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values, strict=True):
        # 必须逆序遍历，防止同一物品被重复使用
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

为什么必须逆序？

• 逆序（capacity -> weight）：当计算 dp[current] 时，依赖项 dp[current - weight] 尚未被当前物品更新，仍保留着“上一轮物品”的状态。这保证了每件物品只被考虑一次。
• 若改为升序：dp[current - weight] 可能已经包含了当前物品的价值，导致同一物品被多次装入，这就变成了完全背包（Unbounded Knapsack）。

复杂度分析

• 时间复杂度：$O(n(C+1))$。
• 空间复杂度：$O(C+1)$（仅求最大价值时）。
• 方案还原：若需输出具体选了哪些物品，需额外记录决策路径或回溯计算。

注意：这是伪多项式时间（Pseudo-polynomial time）。算法复杂度与容量数值 $C$ 成正比，而非与 $C$ 的二进制位数成正比。当 $C$ 极大时，动态规划效率会显著下降。

常见变体辨析

不同变体对应不同的状态转移方程，解题前务必明确约束条件：

• 分数背包（Fractional Knapsack）：允许拆分物品。最优解可用贪心算法（按单位价值排序）求得，无需 DP。
• 完全背包（Unbounded Knapsack）：物品可无限次使用。一维 DP 需改为升序遍历。
• 多重背包（Bounded Knapsack）：每种物品有有限数量限制。通常通过二进制拆分转化为 0/1 背包，或使用单调队列优化。

为什么必须比较选与不选

压缩前，定义 D[i,c] 为只使用前 i 件物品的最优值。最优解要么不选第 i 件，得到 D[i-1,c]；要么在装得下时选它，得到 v_i + D[i-1,c-w_i]。两种情况覆盖全部合法解，移走已选物品后恰好留下所定义的子问题。无物品这一行初始化为零，因为允许什么也不选；这里不要求恰好装满。

重量 [2,3]、价值 [3,4]、容量 5 时，容量 0 到 5 的各行依次为 [0,0,0,0,0,0]、[0,0,3,3,3,3]、[0,0,3,4,4,7]。若升序更新，只处理第一件时就在容量 4 得到价值 6，相当于非法使用两次。

容量和重量须为非负整数，两输入列表等长；zip(..., strict=True) 要求 Python 3.10+。零重量物品在每个容量处只考虑一次，所以正价值也只加一次，包括容量零。升序对应无限使用的解释以正重量为前提；若零重量正价值物品能无限使用，最优值就无界。空输入返回零。容量 6、物品 (重量,价值)=(4,5),(3,3),(3,3) 时，按密度选整件只能得到 5，DP 则选两个重量 3 的物品，得到 6。

assert knapsack([2, 3], [3, 4], 5) == 7
assert knapsack([4, 3, 3], [5, 3, 3], 6) == 6
assert knapsack([0], [5], 0) == 5
assert knapsack([], [], 0) == 0

参考

• CP-Algorithms: Knapsack Problem

我的阅读 · 打开过的笔记会记在当前浏览器里。