從固定比值到一個旋鈕
這之前的四篇導覽，給了你只有單一、要不要隨你的近似比的演算法：頂點覆蓋的貪婪法與 LP 捨入都是 2、集合覆蓋是 ln n、克里斯托菲德斯是 1.5。每一個都是固定的承諾——你拿到的就是那個品質，沒得選。最後這一篇講的是一個嚴格更慷慨的處境。對某些問題，存在的不是一個演算法，而是整整一個由精度旋鈕索引的家族，讓你要多高的精度就要多高，並在多項式時間內交付。那個家族就是近似方案。
這個旋鈕永遠寫作 epsilon（一個小正數），而每個方案的合約都一樣：餵給它你的實例和你選的 epsilon，它就回傳一個在最佳值 (1 + epsilon) 因子之內的解。設 epsilon = 0.1，你就保證在 10% 以內；設 epsilon = 0.01，你就在 1% 以內。當 epsilon 趨近於零，答案就逼近最佳。這在性質上比固定的因子 2 更好：它說這個問題根本沒有任何基本的近似屏障——你願意付多少代價，就能離真正的最佳值多近。
PTAS：對 n 多項式，但要讀細則
兩種方案中較弱的是多項式時間近似方案，即 PTAS。它的承諾：對每個固定的 epsilon，執行時間對輸入規模 n 是多項式。那個固定這個詞分量極重，而它正是初學者吃虧的地方。PTAS 並不承諾執行時間對 n 和 epsilon「一起」是多項式——只承諾一旦你把 epsilon 釘在某個特定值，對 n 的依賴就是一個多項式。對 epsilon 本身的依賴則完全不受限制，而實務上它通常糟糕透頂。
能有多糟？典型的 PTAS 以 O(n^(1/epsilon)) 之類的時間執行——精度旋鈕坐在指數上。看看那會怎樣。在 epsilon = 1/2 時成本是 O(n^2)，完全沒問題。在 epsilon = 1/10（10% 以內）時是 O(n^10)，已經是個重活。在 epsilon = 1/100（1% 以內）時是 O(n^100)，紙面上是多項式，現實中徹底沒指望。所以 PTAS 對每個精度而言誠實地是個多項式時間演算法——但對你通常想要的那種高精度，那個多項式陡到「多項式」這個詞幾乎沒告訴你任何有用的事。這正是反覆出現的漸進分析教訓的銳化版：「對 n 多項式」這個形式藏著一個本身可能隨另一個參數爆炸的指數。
PTAS 從哪裡來？幾乎總是來自一種你能在可調的粒度上利用的結構。一個常見樣式：把實例切成大小由 epsilon 掌控的塊，用暴力法或動態規劃近最佳地解出每一小塊，再把這些塊縫起來、並證明接縫處最多花掉最佳值的 epsilon 分。epsilon 越小表示塊越細，這表示每一塊越大，這正是執行時間膨脹的原因。許多幾何輸入（平面上的點）上的問題與某些排程問題，都能靠這個「切成 epsilon 大小的塊」的想法得到一個 PTAS。
FPTAS：保持便宜的那個旋鈕
PTAS 的瑕疵在於 1/epsilon 可能坐在指數上。完全多項式時間近似方案，即 FPTAS，正好移除這個瑕疵。完全這個單一的詞意味著：執行時間對 n「以及」1/epsilon「一起」是多項式——例如 O(n^2 / epsilon) 或 O(n^3 / epsilon)。現在 1/epsilon 只是個普通的因子，不是指數。把 epsilon 減半（1/epsilon 加倍）也不過讓執行時間的一個因子加倍。高精度真正負擔得起，所以 FPTAS 是在沒有一個精確求解問題的多項式演算法之下，你能擁有的最強之物。
在一個具體要求上比較這兩種方案——解到 1% 以內，所以 epsilon = 0.01。一個在 O(n^(1/epsilon)) 的 PTAS 變成 O(n^100)：一出生就死了。一個在 O(n^2 / epsilon) 的 FPTAS 變成 O(n^2 * 100) = O(100 n^2)：一個二次演算法上的常數乘子，完全實用。同樣的精度要求，兩個天差地遠的世界。「完全」這個精煉的全部用意，就是把 1/epsilon 從指數移到一個多項式因子裡，而這一個動作就是「理論家的好奇心」與「你真會去跑的工具」之間的差別。
造一個出來：背包的捨入與縮放
整個演算法領域裡最乾淨的 FPTAS，是 0/1 背包的那個——每個物品有重量和價值、一個固定容量的背包，最大化裝得下的子集的價值。它是 NP 困難的，但你能在對 n 和 1/epsilon 兩者多項式的時間內，達到最佳價值的 (1 + epsilon) 倍以內。這個構造叫做捨入與縮放，它從你在這條階梯較早遇過的精確背包 DP出發，而關鍵在於其中一個微妙的選擇。背包的 DP 能用兩種方式填：以重量為索引，或以價值為索引。以價值為索引的 DP 對每個可達到的總價值，算出達成它所需的最小重量；它的執行時間對 n 和最大物品價值 V 是多項式。若價值很小這就已經很快——但 V 可能大得驚人，所以這個版本只是偽多項式（對輸入的數值大小是多項式，而非對它的位元長度）。背包整個 NP 困難性就住在那些大數字裡，而捨入與縮放刻意把它們縮小，直到以價值為索引的 DP 變快，同時幾乎不損失什麼。
- 選一個縮放因子 K = (epsilon * V_max) / n，其中 V_max 是最大的單一物品價值。當 epsilon 小時 K 小，當你容忍更多誤差時 K 大——旋鈕直接綁到 K。
- 把每個物品的價值 v_i 換成往下捨入的縮放值 floor(v_i / K)。最大的縮放值現在約是 n / epsilon——小整數，由 epsilon 掌控，而非由原本巨大的 V。
- 在這些捨入後的價值上跑精確的、以價值為索引的 DP。因為價值現在很小，它的執行時間對 n 和 1/epsilon 是多項式——這就是 FPTAS 裡那個「完全」，掙到了。
- 輸出 DP 選的那個子集，但回報它的真實（未捨入）總價值。關鍵是，重量從未被動過，所以這個子集真的裝得下背包。
為何答案在 (1 + epsilon) 之內？把每個價值往下捨成 floor(v_i / K)，每個物品丟掉的價值不到 K。最佳子集最多含 n 個物品，所以整個解上你損失的價值不到 n * K = n * (epsilon * V_max) / n = epsilon * V_max。而真正的最佳至少是 V_max，因為最有價值的單一物品自己就裝得下。所以你放棄的價值最多是最佳值的 epsilon 分：你回傳的子集真實價值至少 (1 - epsilon) * OPT。捨入誤差是對著 OPT 本身界定的——正是貫穿整個這一階的那套「OPT 替身」紀律。
當沒有方案能存在時
誠實要求帳本的另一面：大多數 NP 困難問題沒有 FPTAS，而許多連 PTAS 都沒有。這條界線很鋭利，值得記住。一個強 NP 困難的問題——意思是即使輸入裡所有數字都很小（被 n 的某個多項式所界）它仍是 NP 困難的——除非 P = NP，否則不可能有 FPTAS。推理很乾淨：一個 FPTAS 加上小數字，會讓你能把 epsilon 設得夠細，在多項式時間內釘出精確的整數最佳值，直接解開一個強 NP 困難問題。所以整個捨入與縮放的訣竅，仰賴於難度住在大數字裡，就像背包與子集合加總那樣。
這解釋了你該預期的樣式。背包與子集合加總有 FPTAS，因為它們只因大數字而難——把數字縮小，難度也跟著縮小。但一般（非度量）TSP 與最大團即使輸入很小也難，所以再多的縮放也沒用；事實上一般 TSP 根本沒有任何常數因子近似，更別說方案了。不可近似性結果把這些牆講精確：透過製造間隙的歸約（最終由 PCP 定理驅動），人們證明出像「除非 P = NP，集合覆蓋無法近似得比 (1 - o(1)) ln n 更好」這樣的陳述。這就是為何集合覆蓋卡在 log n、永遠不會有 PTAS——這道屏障是一個定理，不是想像力的失敗。
把常見的提醒放在眼前，因為它們決定該怎麼讀這一切。這些結果每一個都是最壞情況且條件性的：「除非 P = NP 否則沒有 FPTAS」建立在尚未解決的 P 對 NP 問題上，而「難以近似」禁止的是最壞輸入上的好比值，不是你實際面對的實例上的好表現。一個理論上沒有 PTAS 的問題，當某個關鍵參數很小時，實務上仍可能被固定參數演算法馴服，或被不帶保證卻常常奏效的局部搜尋與超啟發式（元啟發式）方法搞定。方案的階層告訴你什麼是可證地可能；當保證用完時，它並不禁止聰明的工程。
一口氣看完整個這一階
退一步看，這五篇導覽構成一道單一的弧。當一個問題 NP 困難，你就停止要求最佳值，改為要求一個可證的、多項式時間的近似——而比值就是合約。有時一個簡單的組合想法就夠：頂點覆蓋取極大匹配的兩個端點、集合覆蓋貪婪地抓最大的未覆蓋集合、度量 TSP 把 MST 加倍。有時你伸手去拿 LP 鬆弛與捨入這套通用機器，它把「OPT 替身」的界對幾乎任何 0/1 問題機械化。而有時問題友善到遞給你一個旋鈕——一個 PTAS，或黃金標準的 FPTAS。
在這每一個底下，坐著的是你如今已見過十幾次的同一個思維動作：你從不去算 OPT——它正是你在閃躲的難題——所以你把答案對著一個便宜、可計算的 OPT 替身（一個匹配、一棵 MST、一個 LP 值、一個捨入後的 DP）去界定。近似的技藝，就是找對替身、並證明你的演算法始終貼著它的技藝。掌握這個動作，「這問題 NP 困難」就不再是死路，而成了一個有趣問題的起點：我能多接近、多快，有沒有一道牆——若有，它究竟立在哪裡？