【近似算法】—0-1背包问题的近似算法
Approximation Schemes(近似方案)PTAS（Polynomial time approximation scheme）定义： FPTAS（Fully polynomial time approximation scheme）定义： PPTAS（Pseudo-polynomial time approximation scheme）定义： 伪多项式时间 0-1背包问题问题描述近似算法解法证明Approximation Schemes(近似方案)
PTAS（Polynomial time approximation scheme）
定义：
若对于每一个固定的 ϵ > 0 ϵ > 0 ϵ>0 ，算法 A 的运行时间以实例 I I I的规模的多项式为上界，则称 A 是一个多项时间近似方案。
FPTAS（Fully polynomial time approximation scheme）
定义：
在 PTAS 的基础上，进一步要求算法 A 的运行时间以实例 I I I的规模和 1 / ϵ 1 / ϵ 1/ϵ 的多项式为上界，则称 A 是一个完全多项时间近似方案。FPTAS 被认为是最值得研究的近似算法，仅有极少数的 NP-hard 问题存在 FPTAS。
PPTAS（Pseudo-polynomial time approximation scheme）
定义：
如果算法的时间复杂度可以表示为输入数值规模 N 的多项式，但是运行时间与输入值规模 N 的二进制位数呈指数增长关系，则称其时间复杂度为伪多项式时间。一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题，而在 P!=NP 的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为强NP完全问题。
伪多项式时间 0-1背包问题
如果数值算法的运行时间是输入数值的多项式，但不一定是输入长度的多项式（表示它所需的位数），则该算法在伪多项式时间内运行0-1背包问题的动态规划算法的运行时间为 O ( W ∗ n ) O(W*n) O(W∗n)， W W W需要 log W \log W logW位来描述，因此它是伪多项式。其他伪多项式算法：原始性测试问题描述
设P为最大利润，即 P = m a x a ∈ S P ( a ) P=max_{a∈S}P(a) P=maxa∈SP(a)。由此，对于 n n n个对象，我们最多获取 n P nP nP的利润上限。在这里，我们可以假设每一项的好处都是内在价值。对于每个 i ∈ { 1 ， … ， n } i∈\{1，…，n\} i∈{1，…，n}和 p ∈ { 1 ， … … ， n P } p∈\{1，……，nP\} p∈{1，……，nP}，设 S i , p S_{i,p} Si,p表示总利润恰好为 p p p的 { a 1 ， … ， a i } \{a_1，…，a_i\} {a1，…，ai}的子集，并且占用尽可能少的空间设 A ( i ， p ) A(i，p) A(i，p)是集合 S i , p S_{i,p} Si,p的大小，其值为 ∞ ∞ ∞，表示没有这样的子集。对于 A ( i ， p ) A(i，p) A(i，p)，我们有基本情况 A ( 1 ， p ) A(1，p) A(1，p)其中 A ( 1 , p ( a 1 ) ) A(1,p(a_1)) A(1,p(a1))是 s ( a 1 ) s(a1) s(a1)，所有其他值都是 ∞ ∞ ∞。近似算法解法
递归式：
然后，最优子集对应于集合 S n , p S_{n,p} Sn,p，其中 p p p最大且 A ( n , p ) ≤ B A(n,p)≤B A(n,p)≤B。由于这最多迭代 n n n个不同的值来计算每个 A ( i , p ) A(i,p) A(i,p)，我们得到了 O ( n 2 P ) O(n ^2P) O(n2P)的总运行时间，因此得到了背包的伪多项式算法很容易修改上述DP算法以实现0-1背包的全多项式时间逼近方案（FPTAS） D P F O R K N A P S A C K ( ) DP\ FOR\ KNAPSACK() DPFORKNAPSACK()
1：Let P be the maximum benefit of all items
2：Given ε > 0 ε>0 ε>0，let K = ε ⋅ P / n K=ε·P/n K=ε⋅P/n。
3：foreach object a i a_i ai do
4：define a new profit p ′ ( a i ) = ⌊ p ( a i ) K ⌋ p'(a_i)=⌊\cfrac{p(a_i)}{K}⌋ p′(ai)=⌊Kp(ai)⌋。
5：将这些 p ′ ( a i ) p'(a_i) p′(ai)作为n个项目的利润，使用动态规划算法，找到最大利润的集合 S ′ S' S′。
6：输出 S ′ S' S′作为原始背包问题的最终解定理：由上述算法输出的集合S′满足： P ( S ′ ) ≥ ( 1 − ε ) ⋅ O P T P(S')≥(1-ε)·OPT P(S′)≥(1−ε)⋅OPT。这里 P ( S ′ ) P(S') P(S′)表示集合 S ′ S' S′的利润（或收益），OPT是原始问题的最佳收益
证明
0-1背包问题近似算法
