背包的 FPTAS（FPTAS for knapsack）

0/1 背包問題：你有一些物品，每個有重量和價值，一個固定容量的背包，你想要裝得下、價值最高的子集。它是 NP 困難的，卻有一個完全多項式時間近似方案——對任何 epsilon，你都能在對 n 和 1/epsilon 兩者多項式的時間內，達到最佳可能價值的 (1 + epsilon) 倍以內。它是「對動態規劃做捨入與縮放」如何把 NP 困難變成任意好的近似最乾淨的具體例子。

這個構造依賴一個關於背包精確 DP 的關鍵事實。填 DP 表有兩種方式：一種以重量為索引，一種以「價值」為索引。以價值為索引的 DP 對每個可達到的總價值，算出達成它所需的最小重量，其執行時間對 n 和最大物品價值 V 是多項式——若價值小就快，但 V 可能巨大，所以這只是偽多項式。馴服 V 的訣竅在此。選一個縮放因子 K = (epsilon * V_max) / n，把每個物品的價值 v_i 換成往下捨入的縮放值 floor(v_i / K)。價值現在是小整數（最大約 n / epsilon），所以以價值為索引的 DP 以對 n 和 1/epsilon 多項式的時間執行。在這些捨入後的價值上精確解背包，輸出那個子集。為何近最佳？我們往下捨入時每個物品的價值減少不到 K，而最佳解最多含 n 個物品，所以損失的總價值不到 n * K = epsilon * V_max。既然真正最佳至少是 V_max（最有價值的單一物品裝得下，假設每個物品單獨都裝得下），損失最多是 OPT 的 epsilon 分。所以捨入後解的真實價值至少是 (1 - epsilon) * OPT。

這是典範的 FPTAS，而模板可推廣：把數字往下縮放讓偽多項式 DP 變快，再把捨入誤差對著 OPT 界定。這裡的誠實在於縮放買到什麼、又花了什麼。捨入「價值」（不是重量）是關鍵——你絕不可違反容量，所以重量保持精確，只有價值被粗化。精度旋鈕 epsilon 直接與執行時間交換：epsilon 越小表示 K 的分母越大、相異價值越多、DP 表越大，全都是多項式地。而這與背包是 NP 困難並不矛盾：FPTAS 在多項式時間內給出近最佳，從不給出精確最佳，所以 P 對 NP 毫髮無傷。