查看“︁0-1背包问题”︁的源代码

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

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

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

== 状态与递推 ==
记 <math>F(i,c)</math> 为只看前 <math>i</math> 件、容量为 <math>c</math> 时的最大价值，容量 <math>c</math> 取从 0 到 7 的整数。这里重量是正整数，价值非负；允许什么都不选，所以 <math>F(0,c)=0</math>。第 <math>i</math> 件重量为 <math>w_i</math>、价值为 <math>v_i</math>。

若 <math>w_i>c</math>，它装不下，故 <math>F(i,c)=F(i-1,c)</math>。若装得下，合法方案恰分两类：不选它，价值至多 <math>F(i-1,c)</math>；选它，剩余容量 <math>c-w_i</math> 只能由'''前 <math>i-1</math> 件'''填，价值至多 <math>v_i+F(i-1,c-w_i)</math>。因此
<math display="block">F(i,c)=\max\{F(i-1,c),\ v_i+F(i-1,c-w_i)\}\qquad(w_i\le c).</math>

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

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

[[File:Gezhi-knapsack-choice.svg|frame|center|alt=容量七且有四件物品时，状态F四逗号七分成不选第四件得到F三逗号七等于九，与选第四件得到八加F三逗号二等于十一；选择后者并回溯到第一件|两条分支穷尽了最后一件的合法决定；选择右支后，剩余容量为 2。]]

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

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

<pre class="algorithm-code">
def knapsack_01(items, capacity):
    if not isinstance(capacity, int) or capacity &lt; 0:
        raise ValueError("capacity must be a nonnegative integer")
    if any(not isinstance(w, int) or w &lt;= 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 &lt;= c:
                take = value + best[i - 1][c - weight]
                if take &gt; best[i][c]:
                    best[i][c] = take

    chosen = []
    c = capacity
    for i in range(n, 0, -1):
        if best[i][c] &gt; 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]
    )
</pre>

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

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/dynamic_programming/knapsack.py TheAlgorithms/Python：knapsack.py]：二维表与回溯的选题参考，本文代码和数值案例独立编写。
* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2008/pages/lecture-notes/ MIT 6.006 动态规划讲义目录]：背包问题与伪多项式时间。
* 先修：[[算法与复杂度]]、[[优化]]；后续：[[动态规划]]。
[[分类:算法]]
[[分类:优化与运筹]]