物品可以分割时:密度与交换
定义 2.9.1
(分数背包与价值密度)
背包容量有限,物品有大小和价值。物品是否允许分割,会改变可以证明正确的算法。先设有有限个物品,大小 ,价值 ;选择比例 ,获得价值 并占用容量 。给定 ,要在 下最大化 。令价值密度 。
算法按密度从大到小排序,依次完整装入物品;遇到第一个不能完整装入的物品,就取恰好填满剩余容量的比例并停止。若所有物品都能装下,就全部装入;若 ,什么都不取。同密度的物品可以任意排序。
定理 2.9.2
(分数背包的贪心规则)
对于上述有限物品、正大小及非负价值,密度排序算法给出最优解。假设精确算术与比较均为常数时间,排序需要 次比较,之后扫描需要 次算术操作。
证明
(把大小转向密度较大的物品)
为什么局部排序足够?可行域是紧致集,故最优解存在。固定排序,设贪心解为 。如果一个最优解首次在位置 与 不同,它在这里只能取得较少:此前相同,而 不是已经等于一,就是用尽了剩余容量。如果某个后续物品 仍取了正比例,可把少量大小 从 转移到 ;选择足够小的 ,使两个比例仍在零到一之间。总大小不变,价值变化是 。每次尽量转移,就能逐步消除后续分配或补足第 项。如果后续没有取任何东西,直接补足第 项仍然可行且价值不减。这样把一个最优解改成与贪心解多一致一项;对有限个位置归纳,得到贪心解也最优。相同密度时交换不改变价值,因此不需要假设密度互不相同。
例题 2.9.3
(允许分割与不允许分割)
容量为 ,三个物品的(大小,价值)为 、、,密度依次是 、、。分数算法完整取第一件,再取任一件大小为五的物品的 ,价值为 。若物品不可分割,后一步不合法;此时取后两件可得价值 ,优于只取第一件所得的 。
交换证明依赖于从后面物品切出恰当大小,再用相同大小的前面物品替换。整件物品无法保证这一步可行。下面保留多种选择,而不把分数规则直接用于零一背包。
零一状态:记住所用物品和容量
定义 2.9.4
(零一背包问题)
现有 个带编号的物品,第 件大小为整数 、价值为整数 ,容量 也是整数。每件至多选一次,即使两件的大小与价值相同,也分别计为不同物品。目标是在总大小不超过容量的子集中取得最大总价值;空集始终可行。以下操作数假设精确算术和比较是常数时间;大整数的位运算成本需另计。
定义 2.9.5
(前缀与容量状态)
对 、,定义 为只使用前 件物品、总大小至多为 时可取得的最大价值。这是“至多”容量:允许有剩余空间。没有物品时 。
仅记录容量并不能说明哪些物品已经被使用;前缀 则把允许使用的物品说清楚。若 ,令 ;否则令
初始化第零行为零,按 依次计算每行的全部容量 ,返回 。为恢复物品,对每个状态保存一个选择位:仅当第二项严格大于第一项时标记“取”,否则标记“跳过”,包括相等或物品放不下的情形。从 开始;遇到“取”就输出 并把 减去 ,每一步都把 减一,到零时停止。
常见错误
(把容量为零的一列初始化为零)
扫描不能漏掉容量零:零大小、正价值的物品可以选一次。因此只有在大小均为正等附加条件下,才能统一写 。对只有一件 、容量为 的情形,正确的值是 ,而把该列初始化为零会得到 。
概念视角结构
把表看作分层图上的最长路径
为每个状态 画一个顶点。对 ,画一条从 到 、长度为 的边(跳过),并在 时画一条从 到 、长度为 的边(取)。从 下降到第零行的每条路径,对每件物品恰好决定一次取或不取,并始终保持在容量之内,路径长度就是所取物品的总价值,所以 是从 到第零行的最长路径。递推式就是每件物品一层的分层图上的最长路径递推式。这解释了为什么每件至多使用一次(每条边都下降一层),也说明恢复只是读出这条路径。
定理 2.9.6
(正确性与资源)
上述算法返回最优价值以及达到该价值的可行子集。表格和选择位占 空间,填表用同阶单位成本操作,恢复用 时间。只求价值时可用 空间。
证明
(按最后一件物品划分子集)
任意最优子集要么不含第 件,价值至多为 ;要么含第 件,因而 ,移除它后得到容量至多 的前 件子集,价值至多为 。这给出两个上界。当 时只有跳过可行;否则,有限个子集保证两个前驱状态都能取得其最优值;前者直接可行,后者加入第 件仍可行,且不可能重复使用该件。因此两项均可达到,取最大值得到正确递推。第零行正确,按 归纳便证明所有表格项,包括零大小和零容量。
恢复时,每个选择位对应填表所用的等值分支。取物品就扣除其大小,然后转到前一行;跳过也转到前一行。所以每件至多取一次,总大小不超原容量。沿选择位反向归纳,所取价值之和正好为 。两项相等时跳过仍可达到最优;另一套一致的平局规则也可能得到不同的最优子集。
证明透视
一件只用一次的规则在何处落实
关键的一步,是从最优子集中删去第 件,进入前缀下标为 的状态。由于前缀下标缩小,第 件不可能再被选取,所以每件只用一次的规则是由递推式的形状落实的,而不是靠额外检查。容量只是被限制,而不是被匹配:剩余部分的大小至多为 ,这正是“至多”状态所接受的。两个方向都需要:上界说明最优值不超过两个选项中的最大者,可达到性则说明它不小于该最大者。对 归纳,从空前缀的一行出发完结论证;零大小并无影响,因为 总是减少。两个选项相等只影响恢复出哪一个子集。
完整算表
例题 2.9.7
(三件互相竞争的物品)
设 依次是 、、,容量为 。第二行最后一格比较跳过第二件所得 ,以及取第二件后加上 所得的 。
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 |
从 开始,跳过第三件,因为 ;在 取第二件,剩余容量二;再在 取第一件。总大小五、总价值七。只取价值最高的单件则只有五。
反例模式
在零一问题中,价值密度不是最优性的凭证
断言:物品不可分割时,按价值与大小之比从大到小取用同样最优。容量为 ,三件物品的(大小,价值)为 、、,比值为 。该规则先取第一件,其后两件都放不下,得到 ;两件大小为五的物品一起却得到 。分数背包的交换论证需要用可分割的后面物品替换前面的物品,这里做不到。修正方法是使用保留各种选择的表 。
例题 2.9.8
(平局与零大小物品的恢复)
设物品依次为 、、,容量为 。在 ,跳过或取第三件的价值都是 ,依照上述平局规则跳过。在 ,取第二件得到 ,大于跳过所得的 ;取它并转到 。此时零大小物品使价值从 提高到 ,所以取它并转到 。所得子集大小为 、价值为 。取第一件虽然不改变容量,行号仍减少,恢复因此终止。改取第三件而不取第二件也是最优解。
压缩表格时,顺序也是证明的一部分
仅求价值时,建立初值全为零的数组 。对每个物品 ,从大到小遍历 ,每个位置只赋值一次:
定理 2.9.9
(单数组更新的顺序)
从第零行出发,处理完第 件后,数组 等于表格的第 行 ,条件是容量 按降序各访问一次,且小于 的容量保持不变。
证明
(降序只读取旧值)
若 ,右侧较小的下标尚未在本轮更新,仍是前一行的值;若 ,右侧读取同一格赋值之前的旧值,而本轮每格只更新一次。因此每处理完一件,数组恰好等于完整表格的对应一行。小于 的容量保持不变。不能对每个格子反复更新直至不再改变。
证明透视
不变量保护的是物品的可用性
二维递推只读取前一物品前缀。降序遍历在一个数组中模拟了这种隔离:需要较小容量时,它还未被本件更新。正确公式与正确循环顺序共同保证每件至多使用一次。
压缩后的最后一行本身也不足以执行上述回溯;应保存完整选择表,或另行证明恢复方法。可变的容量前驱指针未必仍代表旧行,不能直接假定它正确。
反例模式
升序遍历容量会重复使用物品
断言:容量按升序遍历时,单数组更新给出相同的答案。只有一件 ,容量为 时,升序先把 置为 ,再用这个新值更新 ,返回 。同一件被用了两次,而零一最优值是 。修正方法是降序遍历,它只读取旧值。
下面的互动图以两种容量顺序重放压缩更新,并把存储的数值与保留的见证、朴素的可变指针及完整表格回溯互相比较。
数值大小与输入长度
常见错误
(把伪多项式界当作多项式时间)
状态有 个,而非只有 个。时间对容量的数值 是多项式,但二进制表示 只需 位。例如从 增加到 只增加二十位,表格容量维度却约扩大一百万倍。因此该算法称为伪多项式,其操作数并未证明相对于二进制输入长度的多项式时间。任意大的价值相加也须计入位成本。
常见错误
(把不可能的恰好大小初始化为零)
“至多容量”与“恰好装满”不同。恰好大小状态中,无法达到的大小必须标记为不可能,不能全部初始化成零。例如只有一件大小为二时,恰好大小一无法达到,而至多容量一的最优值是零。
构造恰好装满的表
如果要求总大小恰好为 ,定义 为前 件物品中总大小恰好为 的子集的最大价值;用 表示不可能的状态。没有物品时只能达到大小零,因此 ,而 时 。当 时,选择形式仍是
其中约定 ;若 ,则沿用 。证明仍按是否包含第 件划分,但取走该件后剩余大小必须恰好是 。这个标记并非某个子集得到的价值:实际实现时,应先判断前驱是否可能,再做加法。零大小物品仍读取前一行,因此至多取一次。
例题 2.9.10
(恰好大小可能无法达到)
对于物品 和 ,容量从零到五的各行如下:
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 1 | 0 | 5 | ||||
| 2 | 0 | 5 | 4 | 9 |
其中 不可能:跳过第二件需要不可能的 ,取第二件则需要不可能的 。相比之下,至多容量的答案 ,取大小为二的物品并留下两个单位空间。恰好大小五时两件都取,价值为九。求至多容量 时,也可以取大小 中可达到的恰好状态的最大值;不能把不可能状态当成价值为零的解。
练习与解答
快速检查
(物品为 、,容量为三。求最优价值和子集。)
列出所有可行子集。
解答 · 答案
两件一起大小为五,不可行。选第二件,价值五。
快速检查
(物品为 、、,容量为零。求 ;为什么恢复仍会终止?)
零大小物品在容量为零时也放得下。
解答 · 答案
两件零大小物品均可选,价值五;第三件放不下。即使容量不变,恢复时行号每步也减少一。
快速检查
(只有一件 ,容量为二。升序压缩更新返回什么?零一最优值是多少?)
依次追踪两次更新。
解答 · 答案
升序先令 ,再令 ,错误地重复使用物品。正确值为七。
快速检查
(只有一件 ,容量为三。比较至多容量与恰好装满的答案。)
恰好装满的状态需要一个标记值。
解答 · 答案
至多容量的答案是五,留下一个单位空间;恰好大小三不可能达到,应标记为不可能。
快速检查
(容量为零且所有大小为正时,算法返回什么?考虑空物品表。)
考虑 时哪些子集可行。
解答 · 答案
只存在空集可行,答案为零。物品表为空时,第零行就是整个计算。
比较两个模型时,关键是先说明物品能否分割,再核对证明保护的条件。