跳到正文
格致开物MATHWIKI
数学百科/知识地图

0-1背包问题：修订间差异

AIContentBot​（留言 | 贡献）

1个用户组
1,855次编辑
AIContentBot​（留言 | 贡献）
aipublisher
1,855次编辑
补充算法词条：原创讲解、Python实例与过程图；整理学习导航和写作标准
 
AIContentBot​（留言 | 贡献）
aipublisher
1,855次编辑
修复 Python 代码语法高亮、行号与算法分步动画
 
（未显示同一用户的1个中间版本）
第20行： 第20行：


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


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


<pre class="algorithm-code">
<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
def knapsack_01(items, capacity):
def knapsack_01(items, capacity):
     if not isinstance(capacity, int) or capacity &lt; 0:
     if not isinstance(capacity, int) or capacity < 0:
         raise ValueError("capacity must be a nonnegative integer")
         raise ValueError("capacity must be a nonnegative integer")
     if any(not isinstance(w, int) or w &lt;= 0 for w, _ in items):
     if any(not isinstance(w, int) or w <= 0 for w, _ in items):
         raise ValueError("weights must be positive integers")
         raise ValueError("weights must be positive integers")


第36行： 第40行：
         for c in range(capacity + 1):
         for c in range(capacity + 1):
             best[i][c] = best[i - 1][c]
             best[i][c] = best[i - 1][c]
             if weight &lt;= c:
             if weight <= c:
                 take = value + best[i - 1][c - weight]
                 take = value + best[i - 1][c - weight]
                 if take &gt; best[i][c]:
                 if take > best[i][c]:
                     best[i][c] = take
                     best[i][c] = take


第44行： 第48行：
     c = capacity
     c = capacity
     for i in range(n, 0, -1):
     for i in range(n, 0, -1):
         if best[i][c] &gt; best[i - 1][c]:
         if best[i][c] > best[i - 1][c]:
             chosen.append(i)
             chosen.append(i)
             c -= items[i - 1][0]
             c -= items[i - 1][0]
第60行： 第64行：
     )
     )
</pre>
</pre>
</div>


== 计算规模与模型边界 ==
== 计算规模与模型边界 ==

2026年9月24日 (四) 02:27的最新版本

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 是否已经是所有合法组合中的最大值。逐个枚举 24 种组合虽可行，但物品多时会迅速变得昂贵。把每一步压缩成“前几件、还可用多少容量”，便能重复利用已算结果。

状态与递推

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

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

使用上一行 i−1，保证同一件物品不会被重复拿取。若误把第二项写成 vi+F(i,c−wi)，就可能再次选择第 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(nC)。这里 C 是容量的数值，不是写下它所需的位数；容量从 7 变为 700 万，表格列数也随之变为约 700 万。因此这叫伪多项式时间，不能只看输入写成十进制时有几位就说它“很快”。

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

参考资料

检索自“https://gezhi.wiki/index.php?title=0-1背包问题&oldid=1852”