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

形式陈述

从伪多项式算法出发

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

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

(1-\varepsilon)\operatorname{OPT}

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

选择可证明的缩放因子

先丢弃重量超过 $W$ 的物品。令 $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).

最后取满足 $D_n[p]\le W$ 的最大 $p$ ，并沿父决策恢复物品集合。

状态范围 $P'=O(n^2/\varepsilon)$ ，直接实现时间为 $O(nP')=O(n^3/\varepsilon)$ ，空间可用滚动数组降为 $O(P')$ ；若要恢复解，则保存决策或采用重算策略。这个朴素界已经满足 FPTAS 定义，不需要为本原理引入更复杂优化。

直觉

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

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

例子与边界

三件物品的可追踪例子

容量 $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$ ”的损失。最小化问题若照搬同一方向，可能让低估成本的解看似更优，证明方向需要重新设计。价值为有理数时还要说明基本算术成本，不能在实数模型里默认无限精度操作是常数时间。

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

推论与应用

PTAS、FPTAS 与困难边界

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

0/1 背包是弱 NP-hard，并有依赖数值大小的伪多项式 DP，正适合缩放。对强 NP-hard 优化问题，通常不存在这种伪多项式起点；在常见整数目标与复杂度假设下，FPTAS 会导出精确多项式算法，因此除非 $P=NP$ 不应期待同样套路。

参考资料

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.

形式陈述 ​

从伪多项式算法出发 ​

选择可证明的缩放因子 ​

DP 接口与状态演化 ​

三件物品的可追踪例子 ​

舍入损失证明 ​

舍入方向与数值模型 ​

PTAS、FPTAS 与困难边界 ​

反向链接