动机
在 0-1 背包问题中,每个物品有重量和利润,一个解对每个物品至多选取一次,同时总重量不超过容量。以容量为下标的动态规划是精确的,但其运行时间可能与一个以二进制编码的大数成正比。我们可以改为以利润为下标,并有意合并相近的利润。这样以受控的损失换取一个关于输入长度和精度参数倒数的多项式规模的状态空间。
一个看似诱人却不安全的捷径,是按所有物品中的最大利润进行缩放。若该物品比容量还重,它的利润可能远大于任何可行解的利润。此时舍入误差就是相对于一个与最优值毫无关系的数来衡量的。因此第一步是在选定缩放比例之前先丢弃不可行的物品。
定义
输入包含 个物品,其重量 与利润 均为非负整数,以及一个非负整数容量 ,全部以二进制编码。当 时,子集 称为可行;其利润为 。设 为可行子集的最大利润。对于有理数 ,我们要找一个利润至少为 的可行子集。
丢弃满足 的物品。由于重量非负,它们不可能出现在任何可行子集中。丢弃利润为零的物品对最大化利润同样是安全的;包含它们不会改善目标值。若剩余物品中没有正利润物品,则返回空子集。否则剩下 个物品,每个物品单独都是可行的且利润为正。设 为它们的最大利润,则 。
定理
定理 4.5.1
(利润缩放给出 FPTAS)
对每个这样的实例和每个有理数 ,下述算法返回一个利润至少为 的可行子集。其比特运行时间和空间关于二进制输入长度与 均为多项式。
定理 4.5.2
(精确缩放利润下的最小重量)
对非负整数缩放利润 ,定义 为前 个物品中总缩放利润恰为 的子集的最小重量;若不存在这样的子集,则取 。于是
其中下标为负的项取 ,初始条件为 ,且当 时 。
证明
算法与动态规划的证明
令 ,并令 。动态规划对 以及从零到 的每个 计算上述递推式。在每个表项处保留一个取到最小值的前驱选择。取满足 的最大 ,并沿前驱选择回溯,得到对应的子集。
证明
(递推式的正确性)
该递推式对子集作了穷尽的划分:一个子集要么不含物品 ,要么含有物品 ,且其先前部分的缩放利润为 。反过来,把物品 加入任何先前的见证子集,都会得到下标互异的有效子集。对 作归纳即可证明每个有限的表项都等于所述的最小值,并且有相应的见证子集。 的情形按常规处理:包含与不包含两个候选值都引用第 行,因此缩放利润为零的物品在同一行内不会被重复使用。
在实现中,超过 的重量可用哨兵值 表示,加法在此值处封顶。由于重量非负,一个重量已超过 的部分子集以后永远不可能变为可行。哨兵表项不必对应某个重量恰为 的真实子集;它只表示尚未存储任何重量可行的见证子集。所有不超过 的表项都保留有效的见证子集。
近似保证的证明
证明
(近似保证)
设 为一个最优可行子集, 为返回的子集。由于 可行,其缩放总和由某个重量不超过 的表项所表示。算法使可行的缩放总和最大化,因此
对每个物品,。所以
在正利润分支中,一个单独可行的正利润物品保证 非空,因此对各物品的严格不等式求和是合理的。返回的子集由所选表项保证可行,所以其真实利润不可能超过 。当所有可行利润均为零时,单独处理的空子集分支恰好是最优的。
证明透视
对真实最优值的下界抵消了舍入损失
各假设用在哪里:权重非负,才可以丢弃 的物品,使留下的每个物品单独可行,从而 。表的最优性只用一次,用来把返回的缩放总值与固定最优解 的缩放总值比较。关键一步是双边的舍入夹逼 :下侧给出 ,上侧对 的每个物品损失不到 ,而 至多有 个物品。证明之所以闭合,是因为 ,这正是缩放因子 的取法与界 交会之处。若按一个放不进背包的物品的利润来缩放,最后一个不等式就会失效。
状态与比特复杂度
对每个剩余物品,,故 。因此 。表有 行、至多 列,每个表项只需常数次加法和比较。于是表运算的次数为 ,以 为界。
将 写成 ,其中 为正整数。计算
时使用精确的整数乘法和除法。这些整数的比特数关于输入编码是多项式的。封顶后的重量至多有 的比特长度,而下标 需要 个比特。因此标准整数算术既给出多项式的表运算次数,也给出多项式的比特时间。存储所有行和前驱选择只需多项式空间;仅计算数值的话两行就足够,但要还原见证子集则需要额外的重构机制。
概念视角算法
把表格看成最短路径计算
取节点 ,。从节点 到 有一条长度为零的边,到 有一条长度为 的边。于是 就是从 到 的最短路径长度,而每条路径都记录了取了哪些物品。这个递推正是这个分层图上的最短路径更新。
例题详解
例题 4.5.3
(一个小表)
取重量 ,利润 ,容量 ,以及 。两个物品单独都可行,,,。它们的缩放利润为 。表给出 ,,,。最大的可行缩放总和为二,由第二个物品取得,其真实利润为四,这也是最优值。
例题 4.5.4
(舍入改变了所选的子集)
取三个重量均为一的物品,利润为 ,容量为 ,。此时 ,,,缩放利润为 。缩放总和为三的最小重量见证子集只选第三个物品,其真实利润为四。选取全部三个物品是可行的,真实利润为六。该表仍然满足其保证:它使缩放利润最大化,并返回了一个可行子集,尽管舍入使它丢掉了一部分原始的正利润。
例题 4.5.5
(为什么要先移除不可行的物品)
设 ,考虑一个重量为一、利润为二的可行物品,以及一个重量为二、利润为 的物品。重物品不可能出现在可行子集中。若用它的利润进行缩放,在精度参数较粗时,可能使该可行物品的舍入利润变为零。移除它之后,,这是最优值的一个真实下界,近似性的证明便成立。
例题 4.5.6
(零重量与零最优值)
当容量为零时,一个重量为零、利润为七的物品仍然单独可行,不得丢弃。动态规划可以将它包含一次。反之,若所有单独可行的物品利润均为零,则空子集的利润零即为最优值。在该分支中,算法不会除以 。
常见错误
反例模式
以错误的方向原地更新
一个只有一个物品的实例,重量为一,利润为一,容量为二,最多允许得到利润一。若原地递推立即重用刚为同一物品更新过的表项,就会凭空产生利润二。应当分开保存前一行和当前行,或者证明某种更新顺序能防止重复使用;双行递推使 0-1 约束一目了然。
常见错误
(最大化缩放利润不等于最大化真实利润)
使缩放利润最大化并不等同于精确地使真实利润最大化。该方案通过与最优解的比较,证明了后者的一个下界。特别地,对每个固定的缩放值选取重量较小的见证子集是安全的,因为这保持了该值的可行性;任意选取较重的见证子集,则可能使一个可达的缩放值看起来不可行。
常见错误
(把 FPTAS 当作精确的多项式算法)
对 的依赖是结论的一部分。它并非仅关于 的比特长度的多项式。选取指数级小的误差容限,在紧凑编码下可能需要指数级的时间,所以 FPTAS 的存在并不意味着二进制编码的背包问题有精确的多项式时间算法。
理解动态规划的两条坐标轴
常见的以容量为下标的表,问的是在每个允许的重量下所能达到的最大利润。本表则把问题反过来:对每个精确的缩放利润,最小可能的重量是多少?取最小值是正确的概括,因为之后所有物品的重量都非负。对于缩放利润相同的两个部分子集,较轻者为任何后续延伸留下的容量都不少于较重者。它们的真实利润可以不同,但全局的舍入不等式已经考虑了这一差异。
下标表示精确的缩放利润,而不是“至少为 ”的阈值。这一约定使递推式及其初始化没有歧义。无法构成的值保持为不可达;绝不能把每个 都初始化为零。最后对所有精确值的扫描,找出其最小重量满足容量的、最好的可达下标。采用阈值语义的表同样可行,但需要不同的递推式和证明。
界 是连接数值缩放与相对保证的桥梁。相对地, 给出缩放下标的有限范围:剩余的单个利润都不超过 。这两个不等式都用到了预处理。它们的用途不同,也都不能仅由对原始、未经过滤的输入取最大值的定义推出。
在原始实例中验证输出
前驱路径给出一个可审计的原始物品下标列表。要独立验证结果,用整数算术将它们的原始重量和利润相加,检查没有重复的下标,并把重量与原始容量比较。因单独不可行或利润为零而被丢弃的物品不在见证子集中;在所述的非负重量模型下,这对目标值是安全的。近似性的证明针对的是这个原始利润,而不是表中报告的缩放总和。
例如,仅凭缩放值十并不能确定唯一的真实利润。每个被选物品可以贡献不同的舍入余数,且被选物品的个数也有影响。这就是证明为什么先把缩放后的最优值与一个固定的真实最优解的缩放利润联系起来,再用对其所有余数的最坏情形界换算回来。它从不假定舍入保持所有子集利润的大小次序。
若有理精度参数取一,则下界为零,形式上很弱,尽管计算仍可能返回好得多的解。对更小的参数,表随精度的倒数增大而增大。不存在可行正利润物品的预处理情形,避免了缩放比例为零这一无意义的情况,并且无需任何近似算术就返回精确答案。
总结
移除单独不可行以及利润为零的物品,然后用 缩放其余利润。最小重量动态规划找出最优的可行缩放总和并还原出一个子集。至多 次舍入损失,每次小于 ,合计至多损失最优值的 比例。表的状态数与比特长度关于输入和 均为多项式。
练习
快速检查
(设 ,物品的 为 。取 ,计算 与缩放利润,并找出一个缩放意义下的最优解。)
先算 ,再算 。
解答 · 答案
两个物品都可行,故 ,,。缩放利润为一和二。两者一起超过容量;单独取第二个物品具有较大的缩放利润,其真实利润为八。
快速检查
(当 时,为什么重量为零且利润为正的物品不能被丢弃?正确的 0-1 表如何处理它?)
这个物品单独是否可行?
解答 · 答案
它的重量满足限制且能提高利润。无论容量是否为零,递推式都可以从前一行把它包含一次;但它不能在同一行内被重复包含。
快速检查
(设一个可行实例有 ,剩余最大利润 ,且 。求 以及证明中的最大总舍入损失。)
用 与损失界 。
解答 · 答案
。至多五个被选物品,每个损失小于一,所以总损失小于五;这个上界五正好等于 。
快速检查
(若 ,,物品 的重量为二、缩放利润为二,计算 。)
比较递推式中的不取与取两个候选。
解答 · 答案
不包含的候选值为八,包含的候选值为 。因此 。