专题进阶 · 动态规划推荐总顺序 · 第 67 / 148 课

解释容量正序如何允许重复使用同一物品,区分最优值、组合数与排列数。

先学会这些,再进入本课 0/1 背包
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

完全背包Unbounded Knapsack

每件物品可重复使用,一维容量正序允许继承本轮结果。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

解释容量正序如何允许重复使用同一物品,区分最优值、组合数与排列数。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

同样的背包,但每种物品可取任意多件。只有物品 (2,3),容量 4 时为何答案变成 6?

02一步步得到方法

依赖从上一行变成当前行

完全背包选第 i 种物品后,剩余容量仍然允许使用第 i 种,所以二维式为 max(dp[i−1][c],dp[i][c−w]+v)。和 0/1 的关键差别是选择分支依赖当前行。

一维从小到大更新容量,dp[c−w] 可能已加入本种物品,再加一件正好实现不限次数。不能只说正序是模板,要把对应的状态依赖解释清楚。

计数问题还要分清顺序是否重要

本页代码求最大价值,max 不计算方案数。若改为加法计数,物品在外、容量在内通常数不考虑顺序的组合;容量在外、物品在内通常数有顺序的排列。

所有重量必须正数。重量为零且价值为正会使最优价值无界,普通有限 DP 无法表达;输入检查属于数学模型的一部分。

重复使用来自同一层依赖

完全背包允许当前物品继续被选,所以读取 dp[c−w] 时希望它已经包含当前物品的贡献。这正是容量正序的含义,不只是一个需要背诵的循环习惯。

若研究方案数,外层遍历物品还是外层遍历容量还会影响组合与排列的计数语义。最大价值问题与计数问题不能只换一个加号就认为完全等价。

03把一个小例子完全算清楚

物品 (2,3)、(3,4),容量 6。

步骤计算与状态为什么这样做
处理重量 2dp[2]=3,dp[4]=6,dp[6]=9正序使同种累积
处理重量 3dp[3]=4,dp[5]=7可与重量 2 组合
c=6max(9,dp[3]+4=8)=9三件重量 2 更优

窄屏可左右滑动表格,阅读完整计算与理由。

答案 9;重复使用由当前行依赖自然产生。

04为什么这个方法成立

  1. 不选当前种类与至少选一件构成全部方案。
  2. 选择一件后剩余容量仍可选同种,对应 dp[i][c−w]。
  3. 正序保证较小容量当前行已求好,且重量正保证依赖严格向小容量。

05把推导翻译成代码

Python · 可独立运行的教学实现

def unbounded_knapsack(items, capacity):
    dp = [0]*(capacity+1)
    for weight,value in items:
        assert weight > 0
        for c in range(weight, capacity+1):
            dp[c] = max(dp[c], dp[c-weight]+value)
    return dp[capacity]

逐个理解关键决定

range(weight, capacity+1)
从小到大,让本种物品的影响继续向更大容量传播。
assert weight > 0
防止零重量正价值造成数学上的无界最优。

06时间、空间与实现范围

n 种物品、容量 C,时间 O(nC),空间 O(C)。

本版本求不超过容量的最大价值,允许空选择;恰好装满仍需不可达状态。

07改变条件,检查哪里会出错

只把 0/1 代码的名称改成完全背包

必须更改依赖和容量方向,否则仍最多使用一次。

允许零重量且正价值的无限物品

最优价值会无界,必须排除这种输入或明确返回无界状态。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

只有 (3,5),容量 8 得多少?

需要一点提示

最多装两件。

查看解析与答案

10,允许剩余容量 2。

练习 2 · 边界与辨析

面值 1、2,金额 3,组合数与排列数各几种?

需要一点提示

1+2 与 2+1 是否算不同?

查看解析与答案

组合 2 种:1+1+1、1+2;排列 3 种,多了 2+1。

练习 3 · 变式与迁移

不限次数但要求至少一件,负价值怎么办?

需要一点提示

初值 0 会选空集。

查看解析与答案

需要额外状态或初始化约束;先改数学问题定义,再改代码,不能只在答案上补一个判断。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。