动机
看起来最划算的当前选择,可能留下难以处理的余数。用面值一、三、四的硬币凑六,每次取不超过余数的最大面值,会得到四、一、一;但两个三只需两枚硬币。贪心结果可行,却不因此最优。
动态规划把一次选择变成一族定义精确的子问题。我们列出所有备选情况,证明它们涵盖每个解,再按依赖已知的次序填表。表格不只能给出数值:保留合适的选择,还可以恢复一个实际解。
有限 0–1 选择问题
有 个按下标区分的物品。第 个物品有正整数重量 和整数价值 ,至多选一次。非负整数容量 限制总重量。允许空集,目标是在总重量至多为 时最大化总价值。价值可以为负;空集保证最优值至少为零。即使两个物品重量或价值相同,也按下标区分。
定义 3.6.1
(前缀—容量状态 )
对 、, 是只用前 个物品、容量至多为 时可获得的最大价值。不同前缀和容量对应不同状态。特别地,对每个 有 ;由于重量为正,还有 。
定理 3.6.2
(0–1 递推)
对 ,若 ,则 。否则
按物品顺序递增填表,便得到最优值 。即使有多个并列最优子集,完整表格也支持恢复其中一个。
如何得到状态转移
证明
(按最后一个物品分类,再对行数归纳)
前 个物品的每个可行子集,或者不含第 个物品,或者含它。第一种情况下价值不超过 ,并且某个旧状态最优子集能达到此界。第二种只有 时才可能;删除第 个物品后,余下的是前 个物品中容量至多为 的子集,其价值因而不超过第二个候选。反过来,把第 个物品加到实现该候选的最优子集上,不会重复使用任何物品。两个候选中的较大者既可达到,又不小于任何可行子集的价值。
基础行只允许空集。归纳地,只要前一行正确,当前行也正确。如果完整前一行保持不变,一行内部的容量可以按任意顺序访问。状态中的容量含义是至多,不要求恰好填满。若把基础行除零容量之外都设为不可能,就改变成了另一种恰好重量问题。
恢复解时从 出发。若当前项等于正上方的项,略过该物品并移到前一行;否则该物品必定装得下,且第二候选取到最大值:选入它,从容量减去其重量,再移到前一行。并列时略过是有效选择。行号每步递减,所以至多 步得到互不重复的物品,其总价值就是最终表项。仅保留最优数值,没有选择或旧行,本身并不是重建方法。
证明透视
背包证明中每个假设在哪里用到
唯一的关键是按最后一个物品划分:“不选第 个物品”与“选第 个物品”覆盖所有可行子集且互不重叠,所以两种情况各自的最大值中较大者,就是全部子集的最大值。每种情况都由两个不等式完成:该情况中每个子集的上界,以及由较小状态的最优解构造出的可达子集。第二候选读取的是第 行而非第 行;正是这个下标使加入后的子集只用第 个物品一次。若改读 ,便允许第二个副本,证明的就是另一个可无限复制问题的递推。
重量为正用了两次:它给出 ,并使 严格较小,后面的压缩扫描需要这一点。归纳是对行号进行的,所以计算次序只需在第 行之前完成第 行。重建能够结束也出于同一结构:每一步都移到第 行;并列时,上方的项本身由前 个物品的某个子集达到,所以略过绝不损失价值。
压缩表格时如何避免重复选取
一维数组在每个容量处初始为零。对每个物品,从 向下遍历到 ,把当前项更新为自身与容量 的项加 二者的最大值。由于 ,较小容量在本物品的下降扫描中尚未访问,仍保存前一行的值。因此更新恰好实现上述递推。若 ,该物品没有更新。
若反过来递增扫描,较小容量可能已包含同一物品,读取时数组存放的就不再是第 行。一行用 个存储项可计算最优值,但要直接使用前述方法恢复解,还需旧行或其他经过证明的附加信息。
反例模式
递推正确,更新次序仍可能错误
断言:原地扫描可以按任一方向访问容量。取一个重量二、价值三的物品,容量四,数组按容量 为 。递增扫描把容量二设为 ,容量三设为 。到容量四时,它读取已被改写的容量二,存入 。可行子集只有空集与该物品本身,价值分别为零和三,所以真实最优值是三:扫描把物品用了两次。下降扫描先计算容量四,所读容量二仍是未改动的零,结果为三。修正后的表述:对 0–1 问题,扫描必须由 向下到 ;递增扫描是可无限复制问题的递推。
另一种状态:恰好凑数的最少硬币
现在设面值 均为正整数,每种可无限使用,目标数额为 。我们要求总和恰好为 的最少硬币数;目标也可能无法凑出。
定义 3.6.3
(精确最少硬币状态 )
对 , 是总和恰好为 的最少硬币数;无法表示时记 。基础值为 。
定理 3.6.4
(精确最少硬币递推)
对 ,
其中空集合的最小值为 ,且 。按 的次序计算后, 就是最少数或正确的不可能报告。
证明
(移除最后一枚硬币)
凑出正数 的每种表示都有最后一枚硬币,设面值为 。移除它得到 的表示,所以原硬币数至少为相应候选。反过来,只要较小状态有限,加入所选硬币就达到该状态计数加一。若没有任何较小状态有限,就不存在表示。两方向不等式与对 的归纳证明了递推。面值为正至关重要:每个依赖都严格更小,恢复解也不会停在同一数额。
在每个正且可达的数额处,保存一个达到有限最小值的面值。从 开始,反复输出所存硬币并减去其面值。剩余数额严格下降,最终到达零;沿记录的前驱,计数每次减少一。所得列表恰有 枚硬币。当 时返回空列表;若 ,应报告无法表示,而不是尝试回溯。
硬币顺序不影响最少枚数,所以把某枚称为“最后一枚”只是证明工具。如果问题改为计数,区分有序序列与无序多重集就需要不同状态或循环约定;仅凭最少数递推不能决定那个计数问题。
概念视角结构
两个表格都是无圈图中的路径
在每个数额 放一个顶点;只要 ,就从 到 连一条长度为一的边。总和为 的硬币序列,恰好是一条由 到 的有向路径,其长度就是硬币数。因此 是由 到 的最短路径距离, 表示到不了 。每条边都使数额减少,所以图中没有圈,而次序 把每个顶点排在它所指向的全部顶点之后。
背包表格有同样的形状。由 连一条权为零的边到 ;当 时,再连一条权为 的边到 。由 到第零行的路径,每个物品至多选一次,所用重量至多为 ;每个可行子集也给出这样一条路径。因此 是到第零行的最大路径权,而重建就是找回一条最优路径。
成本与输入含义
命题 3.6.5
(表格大小与运算次数)
完整背包表有 项,用 次精确操作构造;由它重建至多需 步。下降的一行数值算法使用 个存储项。找零表格需要 次精确操作及 个存储项,包括每个数额保存一个前驱。
每个背包表项用常数次比较及加法计算,每个找零表项至多比较 个候选;连同初始化便得到上述次数。输出硬币列表还需与其长度成比例的时间。
这些界是伪多项式的:它们依赖容量或目标的数值,而该数值可能比其二进制编码长度指数地大。若整数物品价值的绝对值至多为 ,每个有限背包表项的绝对值至多为 ,所以算术位长为 。每个有限找零计数至多为 ,因为面值至少为一。无穷大用独立标志表示。比较、加法、索引和输入存储都须按表示方式计费;表项数量本身不能保证无界整数运算为常数时间。
为什么不依靠贪心也能保证最优值存在
0–1 问题只有有限多个子集,所以即使有负价值,最大值也存在。找零中每个面值至少为一,任何凑出 的表示至多含 枚硬币;如此有界长度的可能序列只有有限多个。只要存在表示,最少数就能取到。递推依赖的是这些极值和完整分类,而不是“局部最佳的第一步一定能扩展为全局最优”的断言。
例题
例题 3.6.6
(0–1 最优值及其见证)
取重量 、价值 、容量六。物品一和三恰好装满,总价值十一;物品一和二价值九,二与三超重,三个物品也超重。任何单件都不更好,所以最优值是十一。沿完整表回溯可返回下标一和三。
例题 3.6.7
(先取最大硬币可能失败)
面值为一、三、四,目标为六。最大面值规则取四、一、一,共三枚。表中有 ,因此用两个三得到 。面值中没有六,不可能只用一枚,故 。这个反例并不声称贪心对所有面值系统都失败。
例题 3.6.8
(能整除仍可能无法凑出)
面值四和六的最大公因数为二,但不能用它们的非负个副本凑出目标二。表中 、。目标被最大公因数整除是可表示的必要条件,却不足以保证某个较小的非负目标可表示。
常见错误与范围
常见错误
(“至多”容量不是精确目标)
允许容量有剩余。一个重量二、价值五的物品,容量三时 。若把基础行除零容量外都设为不可能,表格问的便是重量恰好为三,而这个物品做不到。基础行必须配合所要解的问题。
常见错误
(哨兵值不是硬币数)
用一个很大的有限数 表示不可能,会把 变成 ;它可能参与比较、溢出,或被当成计数输出。加一之前先检查是否不可能,把无穷大保留为独立标志,并报告无法表示,而不是从它回溯。
常见错误
(最优值不是见证)
数值 并没有指出哪个子集,而且可能有多个子集并列。恢复的答案必须列出所选物品或硬币,并核对其总和等于表项;只保留一行压缩表时,这需要另外保存选择。
本节证明的是两种明确模型的精确离散优化,不由此得到一般贪心定理、以二进制输入长度衡量的多项式界、浮点误差保证或最优解个数公式。零或负面值及零重量物品需要另行指定模型,这里不包含。
小结
动态规划首先明确状态及全部相关限制,再用完整分类得到递推;归纳与尊重依赖的计算次序证明表格正确。保存前驱信息后,最优值可以转化为可核验的物品选择或硬币列表;数值范围则解释了伪多项式成本。
练习
快速检查
(物品重量为 ,价值为 。容量为五时,求最优值及一个达到它的子集。为何容量为零时价值为零?)
解答 · 答案
物品一和二总重量五、总价值九。单选物品三价值七,其余配对和三件一起都超重。因此九是最优值,由下标一和二见证。容量零排除所有正重量物品,空集给出价值零。
快速检查
(只有一个 0–1 物品,重量二、价值三。容量为四时,向下和向上原地扫描分别返回什么?哪一个符合所述模型?)
解答 · 答案
下降扫描返回三:计算容量四时,容量二仍是旧值零。上升扫描先在容量二写入三,又错误地重复利用它,在容量四得到六。三才是正确的 0–1 最优值;六使用了两次同一个物品。
快速检查
(使用面值四和六。求 、 和 ,若能表示则恢复一个最少硬币表示。)
解答 · 答案
空列表给出 。两种面值都超过二,所以 。两个四可以凑八,而一枚硬币不行,因此 ,见证是四加四。
快速检查
(若容量为 ,为何每个容量存一项的表不意味着关于位长 的多项式界?完整表回溯使用什么额外数据?)
解答 · 答案
容量只需 个二进制数字,表中却有 个容量位置。表长对 为指数级,因此此界不是关于二进制输入长度的多项式界。完整表回溯将当前项与前一行比较,必要时记录选入,并移到前一行的较小容量状态。