0-1背包问题

0-1 背包问题给定若干物品，每件有重量和价值，在总重量不超过容量的条件下使价值最大。每件只能选一次，因此决策是“选”或“不选”，不能把同一件物品分成小份。它是动态规划中很适合手算状态的例子，也与优化中的约束选择相连。

四件物品的选择

设容量为 7，四件物品的重量依次是 2、3、4、5，价值依次是 3、4、5、8。选第 1 件和第 4 件，总重量 $2 + 5 = 7$ ，总价值 $3 + 8 = 11$ 。第 2、3 件同样装满，价值却只有 $4 + 5 = 9$ 。逐项按照“价值/重量”从高到低贪心选，在别的数据上也可能失手：容量 50，三件物品为 $(10, 60), (20, 100), (30, 120)$ ，贪心先选重量 10、20 的两件得到 160，而重量 20、30 的两件得到 220。

对四件物品的例子，真正需要确认的是：11 是否已经是所有合法组合中的最大值。逐个枚举 $2^{4}$ 种组合虽可行，但物品多时会迅速变得昂贵。把每一步压缩成“前几件、还可用多少容量”，便能重复利用已算结果。

状态与递推

记 $F (i, c)$ 为只看前 $i$ 件、容量为 $c$ 时的最大价值，容量 $c$ 取从 0 到 7 的整数。这里重量是正整数，价值非负；允许什么都不选，所以 $F (0, c) = 0$ 。第 $i$ 件重量为 $w_{i}$ 、价值为 $v_{i}$ 。

若 $w_{i} > c$ ，它装不下，故 $F (i, c) = F (i - 1, c)$ 。若装得下，合法方案恰分两类：不选它，价值至多 $F (i - 1, c)$ ；选它，剩余容量 $c - w_{i}$ 只能由前 $i - 1$ 件填，价值至多 $v_{i} + F (i - 1, c - w_{i})$ 。因此 $F (i, c) = max {F (i - 1, c), v_{i} + F (i - 1, c - w_{i})} (w_{i} \leq c) .$

使用上一行 $i - 1$ ，保证同一件物品不会被重复拿取。若误把第二项写成 $v_{i} + F (i, c - w_{i})$ ，就可能再次选择第 $i$ 件，求成另一个“可无限取同类物品”的问题。

最后一格的两个分支

处理到第 3 件、容量 7 时，最优是第 2、3 件，得到 $F (3, 7) = 9$ 。若第 4 件不选，最终仍是 9；若选重量 5、价值 8 的第 4 件，前 3 件只剩容量 2，只能再取第 1 件，得到 $8 + F (3, 2) = 8 + 3 = 11$ 。所以 $F (4, 7) = 11$ ，并能反向找回第 1、4 件。

容量七且有四件物品时，状态F四逗号七分成不选第四件得到F三逗号七等于九，与选第四件得到八加F三逗号二等于十一；选择后者并回溯到第一件 — 两条分支穷尽了最后一件的合法决定；选择右支后，剩余容量为 2。

递推的正确性可以对 $i$ 归纳：没有物品时最优值确为 0。假设前 $i - 1$ 件在每个容量下的值都正确；任一使用前 $i$ 件的合法方案必属于上面的“选”或“不选”一类，而两类各自的最好值由归纳假设给出。取较大者既能达到，又不可能被同类方案超过，故 $F (i, c)$ 正确。

0-1 背包的逐行选择

对每件物品比较选与不选，最后回溯所取物品。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

代码把表格各行保留下来，以便从最后一格回溯出物品编号。编号从 1 开始；相同最优价值有多个组合时，等值情况下优先“不选当前物品”，只返回其中一组。

Python 3

def knapsack_01(items, capacity):
    if not isinstance(capacity, int) or capacity < 0:
        raise ValueError("capacity must be a nonnegative integer")
    if any(not isinstance(w, int) or w <= 0 for w, _ in items):
        raise ValueError("weights must be positive integers")

    n = len(items)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i, (weight, value) in enumerate(items, start=1):
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]
            if weight <= c:
                take = value + best[i - 1][c - weight]
                if take > best[i][c]:
                    best[i][c] = take

    chosen = []
    c = capacity
    for i in range(n, 0, -1):
        if best[i][c] > best[i - 1][c]:
            chosen.append(i)
            c -= items[i - 1][0]
    chosen.reverse()
    return best[n][capacity], chosen


if __name__ == "__main__":
    items = [(2, 3), (3, 4), (4, 5), (5, 8)]
    assert knapsack_01(items, 7) == (11, [1, 4])
    assert knapsack_01(items, 0) == (0, [])
    assert knapsack_01([], 7) == (0, [])
    assert knapsack_01([(10, 60), (20, 100), (30, 120)], 50) == (
        220, [2, 3]
    )

计算规模与模型边界

有 $n + 1$ 行、 $C + 1$ 列，每格至多比较两个候选值，所以时间和保存完整表格的空间都是 $O (n C)$ 。这里 $C$ 是容量的数值，不是写下它所需的位数；容量从 7 变为 700 万，表格列数也随之变为约 700 万。因此这叫伪多项式时间，不能只看输入写成十进制时有几位就说它“很快”。

若只要最优价值，可以用从大容量向小容量更新的一维表，把额外空间降到 $O (C)$ ；若还要像本例这样找回选了哪些物品，保留二维表更容易审查。重量不是整数或容量巨大时，不应直接套用这里逐容量枚举的表格；需要重新选状态、缩放策略或其他优化方法，并说明误差与条件。

参考资料

TheAlgorithms/Python：knapsack.py：二维表与回溯的选题参考，本文代码和数值案例独立编写。
MIT 6.006 动态规划讲义目录：背包问题与伪多项式时间。
先修：算法与复杂度、优化；后续：动态规划。