容量有限、每件物品拿或不拿：NP-Hard 卻有偽多項式解法的代表作

難度定位

• 判定版本（「價值能否 \(\geq V\)？」）是 NP-Complete（可由 Subset Sum 歸約）。

• 但它有 \(O(nW)\) 的 DP——與輸入的數值 \(W\) 成正比而非與輸入長度（\(\log W\) 位元）成正比，所以叫偽多項式（pseudo-polynomial）。\(W\) 是一億時照樣跑不動。

• 屬於弱 NP-Hard：數值小就簡單，數值大才難。這與 TSP 那種強 NP-Hard（數值再小也難）形成對比。

演算法一：動態規劃 \(O(nW)\)

狀態設計

\[dp[i][c] = \text{只考慮前 } i \text{ 件、容量 } c \text{ 時的最大價值}\]

第 \(i\) 件只有兩種命運：

\[dp[i][c] = \max\bigl(\underbrace{dp[i-1][c]}_{\text{不拿}},\ \underbrace{dp[i-1][c-w_i] + v_i}_{\text{拿（需 } c \geq w_i\text{）}}\bigr)\]

答案是 \(dp[n][W]\)。時間 \(O(nW)\)、空間 \(O(nW)\)（保留全表才能還原方案）。

手算範例

物品 \((w,v)\)：A\((2,3)\)、B\((3,4)\)、C\((4,5)\)、D\((5,8)\)，\(W=10\)。表格橫軸容量、縱軸物品（只列關鍵欄）：

\(dp[4][10]=15\)：反推方案時逐列比對「值有沒有變」。\(dp[4][10]=15 \neq dp[3][10]=12\)，表示 D 有拿（剩容量 \(10-5=5\)）；\(dp[3][5]=7 = dp[2][5]\)，值沒變表示 C 沒拿；\(dp[2][5]=7 \neq dp[1][5]=3\)，表示 B 有拿（剩容量 \(5-3=2\)）；\(dp[1][2]=3 \neq 0\)，表示 A 有拿。方案 = {A,B,D}，重 \(2+3+5=10\)、值 \(3+4+8=15\)。

一維空間優化

觀察轉移只用到上一列，可以壓成一維——但容量必須由大到小掃，否則同一件物品會被拿兩次（那是無限背包的寫法）：

for (const auto& it : items)
    for (int c = W; c >= it.w; --c)      // 倒序！
        dp[c] = max(dp[c], dp[c - it.w] + it.v);

演算法二：分支限界（Branch and Bound）

當 \(W\) 太大 DP 開不了表時，回到搜尋，但帶上「樂觀估計」剪枝。

上界函數

在節點（已決定前 \(k\) 件）估計「剩下的物品最多還能貢獻多少」：把剩餘物品依價值密度遞減排序，允許切割地裝滿剩餘容量（分數背包鬆弛）。分數背包的最優值 \(\geq\) 0/1 的最優值，所以這是合法上界：

\[\text{if } \underbrace{\text{目前價值}}_{val} + \underbrace{\text{分數鬆弛上界}}_{bound} \leq \text{已知最佳} \Rightarrow \text{整枝剪掉}\]

效果

本篇程式 Example 3（\(n=30\)、\(W=500\)）：DP 檢查 \(30 \times 500 = 15000\) 格；分支限界只拜訪 59 個節點。物品先按密度排序讓好解早出現、上界更快收緊，是剪枝威力的關鍵。

完整 C++ 程式

包含：二維 DP + 方案還原、一維優化 DP、分數鬆弛分支限界、偽多項式行為實測。編譯：

g++ -std=c++17 -O2 -Wall -Wextra -o knapsack knapsack.cpp

執行結果與解讀

=== Example 1: classic 3-item case ===
W=50, items (w,v) = (10,60)(20,100)(30,120)
best value = 220 (expect 220)
chosen items: #1(w=20,v=100) #2(w=30,v=120)
1D DP check = 220

=== Example 2: 6-item worked example ===
W=10 -> best = 15, chosen: #0 #1 #3  (total w=10, v=15)

=== Example 3: DP vs branch-and-bound (n=30, W=500) ===
DP  : best=1345  (0.014 ms)
B&B : best=1345  (0.004 ms, nodes=59)
agree = yes

=== Example 4: pseudo-polynomial blow-up ===
W=1000     -> best=1687  (0.031 ms)
W=100000   -> best=1687  (2.80 ms)
W=10000000 -> best=1687  (288.9 ms)
(n fixed at 30; time grows linearly with W, the VALUE)

實務應用

• 資源分配：預算 \(W\) 元投資 \(n\) 個專案（各有成本與預期收益），選哪些？

• 雲端資源打包：把工作負載塞進固定規格的 VM，最大化利用率。

• 廣告投放：版位容量有限，挑選收益最高的廣告組合。

• 密碼學淵源：早期的 Merkle–Hellman 背包公鑰系統基於 Subset Sum 難度（後來被破，但歷史意義重大）。

• FPTAS：背包有完全多項式時間近似方案——把價值除以 \(K\) 取整再跑 DP，可在 \(O(n^3/\varepsilon)\) 內保證 \((1-\varepsilon)\) 最優。弱 NP-Hard 問題的專屬福利。

練習題

1. 用一維 DP 求 \((w,v)\) = \((1,1),(3,4),(4,5),(5,7)\)、\(W=7\)，並手動還原方案（提示：一維表無法直接還原，需要另存決策或改用二維）。

2. 把程式改成無限背包（每件可拿多次）：只需把一維 DP 的容量迴圈改成正序。驗證 \((2,3)\) 單件物品、\(W=10\) 時答案是 15。

3. 實作 FPTAS：價值縮放 \(K = \varepsilon \cdot v_{\max} / n\)，用 \(\varepsilon=0.1\) 對照精確解的誤差。

4. 分支限界目前用「先拿再不拿」的順序分支，改成「先不拿」會怎樣？實測節點數。

5. 挑戰：二維背包（重量與體積雙限制）\(O(nWV)\) DP。

小結

延伸閱讀：Kellerer, Pferschy, Pisinger Knapsack Problems（背包問題的百科全書）；Martello & Toth Knapsack Problems: Algorithms and Computer Implementations。