通过缩放构造 FPTAS | Codeboy's Blog

形式陈述

从伪多项式算法出发

0/1 背包有物品 $i=1,\ldots,n$ ，以二进制给出的非负整数重量 $w_i$ 、价值 $v_i$ 和容量 $W$ ，物品表显式列出。目标是在总重量不超过 $W$ 时最大化总价值。按总价值做动态规划的时间取决于 $\sum_i v_i$ ，对数编码输入下只是伪多项式。

FPTAS 给定有理数 $0<\varepsilon<1$ ，在输入长度与 $1/\varepsilon$ 的多项式时间内返回价值至少

(1-\varepsilon)\operatorname{OPT}

的可行解。缩放的目的不是让价值“看起来更小”，而是把 DP 状态数变成由 $n/\varepsilon$ 控制。

选择可证明的缩放因子

先丢弃重量超过 $W$ 的物品，并从现在起以 $n$ 表示剩余件数。若 $n=0$ ，返回空集；否则令 $V_{\max}$ 为剩余物品的最大价值；若没有正价值可行物品，空集就是最优解。否则单个最大价值物品可行，所以

V_{\max}\le\operatorname{OPT}.

取

K=\frac{\varepsilon V_{\max}}{n},\qquad v'_i=\left\lfloor\frac{v_i}{K}\right\rfloor.

向下取整保证缩放值不会高估物品贡献。每个 $v'_i\le n/\varepsilon$ ，故所有缩放价值之和至多 $n^2/\varepsilon$ 。

DP 接口与状态演化

令 $D_i[p]$ 表示前 $i$ 个物品取得缩放总价值恰为 $p$ 所需的最小重量。初始 $D_0[0]=0$ ，其余为无穷大；转移为

D_i[p]=\min\bigl(D_{i-1}[p], D_{i-1}[p-v'_i]+w_i\bigr).

若 $p-v'_i<0$ ，选入项视为无穷大；所有有限项都只读取上一行，即使 $v'_i=0$ 也不重复使用同一物品。最后取满足 $D_n[p]\le W$ 的最大 $p$ ，并沿各行父决策恢复物品集合。

状态范围 $P'=O(n^2/\varepsilon)$ ，直接实现时间为 $O(nP')=O(n^3/\varepsilon)$ ，空间可用滚动数组降为 $O(P')$ ；若要恢复解，则保存决策或采用重算策略。这些是表格访问、重量加法与比较的次数；完整父决策表占 $O(nP')$ 空间。可把超过 $W$ 的重量统一截为 $W+1$ ，每格只需 $O(\log(W+2))$ 位。缩放因子和取整用有理整数算术精确计算，加入原输入与精度编码的多项式位成本后，仍满足 FPTAS 的联合多项式要求。

直觉

缩放用每件至多 $K$ 的价值损失换取有限的整数状态空间。最优解至多含 $n$ 件物品，所以总舍入损失至多 $nK$ ；把 $K$ 绑定到一个可证明不超过 OPT 的 $V_{\max}$ ，就能同时控制误差比例与 DP 表宽度，而不是凭经验删去价值精度。

价值缩放和向下取整把伪多项式 DP 压缩为精度控制的窄状态表 — 价值缩放、DP 窄化与误差界

图另取价值 $(1000,850,620)$ 、 $\varepsilon=0.3$ 、 $n=3$ ，所以 $K=100$ ，缩放价值为 $(10,8,6)$ 。例如配重量 $(4,3,2)$ 和容量 $5$ ，三件都单独可行， $V_{\max}=1000\le OPT=1470$ 。条末的 $2470$ 与 $24$ 是最大总价值下标；若连同下标 $0$ 计数，分别对应 $2471$ 与 $25$ 格。

例子与边界

三件物品的可追踪例子

容量 $W=5$ ，物品 $(w_i,v_i)$ 为

(4,10),\quad(3,8),\quad(2,6),

取 $\varepsilon=1/4$ 。此时 $V_{\max}=10$ ，

K=\frac{(1/4)\cdot10}{3}=\frac56,

缩放价值分别为 $12,9,7$ 。

DP 发现第二、三件总重量 $3+2=5$ ，缩放总价值 $9+7=16$ ；第一件单独只有 12，因此返回后两件。其真实价值为 14。例子中它恰好是最优解，但 FPTAS 的一般保证只要求达到 $(1-\varepsilon)\operatorname{OPT}$ 。

舍入损失证明

设 $O$ 是最优物品集，算法返回 $A$ 。因为 DP 在缩放实例上最优且 $O$ 仍满足重量约束，

\sum_{i\in A}v'_i\ge\sum_{i\in O}v'_i.

又因 $K\lfloor v_i/K\rfloor>v_i-K$ ，有

\sum_{i\in A}v_i \ge K\sum_{i\in A}v'_i \ge K\sum_{i\in O}v'_i > \operatorname{OPT}-|O|K.

使用 $|O|\le n$ 与 $nK=\varepsilon V_{\max}\le\varepsilon\operatorname{OPT}$ ，得到

\sum_{i\in A}v_i \ge(1-\varepsilon)\operatorname{OPT}.

这一步解释了为什么必须给出 $V_{\max}\le\operatorname{OPT}$ 的下界关系。若随意以所有价值之和设 $K$ ，累计舍入损失可能大于 $\varepsilon\operatorname{OPT}$ 。

舍入方向与数值模型

最大化价值时向下取整便于控制“每件少于 $K$ ”的损失。最小化问题若照搬同一方向，可能让低估成本的解看似更优，证明方向需要重新设计。有限非负有理价值也可直接按同一公式得到整数 $v'_i$ ；有理重量与容量可统一乘分母的最小公倍数，分母位长之和控制所得整数位长。此时原始价值本身不能直接作为整数 DP 下标，仍须先缩放取整。任意实数 oracle则是另一种计算模型，不能默认无限精度算术具有上述有限编码成本。

容量、重量无需按同一因子缩放；本构造保留原重量，因此返回解天然可行。若改为缩放重量，就必须另外处理容量超出或资源增广，保证形式会不同。

容量 DP 的编码账单在旧精确算法一侧给出全部状态与54位输入实例；阈值与见证恢复用同一三件物品复算最优值14和选择011。共同终点再使用本页已有的 $K=5/6$ 、缩放价值 $(12,9,7)$ 与舍入证明，比较精确判定、近似输出和容量数值的三种成本。

推论与应用

PTAS、FPTAS 与困难边界

PTAS只要求对每个固定 $\varepsilon$ 多项式，指数可以依赖 $1/\varepsilon$ ；FPTAS 要求对 $n$ 和 $1/\varepsilon$ 联合多项式。上面的 $O(n^3/\varepsilon)$ 明确满足后者。

0/1 背包是弱 NP-hard，并有依赖数值大小的伪多项式 DP，正适合缩放。排除强 NP-hard 问题的 FPTAS 还要明确目标值的界。例如在一族仍 NP-hard 的受限整数最大化实例上，以 $N$ 记完整编码长度，若已知 $0\le OPT\le B(N)$ 且 $B$ 是正的多项式界，那么取 $\varepsilon=1/(2B(N))$ 会让返回的整数价值距最优小于 $1$ ，因而必须精确最优；FPTAS 的时间在这一精度下仍为多项式。这才是在 $P\ne NP$ 假设下排除相应方案的量化理由，不能只凭“强 NP-hard”四个字省略目标编码与界。

参考资料

Oscar H. Ibarra and Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM, 1975.
Vijay V. Vazirani, Approximation Algorithms, Springer, 2001.
Hans Kellerer, Ulrich Pferschy and David Pisinger, Knapsack Problems, Springer, 2004.
David P. Williamson、David B. Shmoys，The Design of Approximation Algorithms，2011，§3.1：按价值的动态规划、缩放取整与 FPTAS 证明；本页另外处理零重量、零价值和空输入。

形式陈述 ​

从伪多项式算法出发 ​

选择可证明的缩放因子 ​

DP 接口与状态演化 ​

三件物品的可追踪例子 ​

舍入损失证明 ​

舍入方向与数值模型 ​

PTAS、FPTAS 与困难边界 ​

反向链接