為何貪婪在 0/1 背包失敗（0/1 knapsack greedy failure）

回想可分割（分數）背包，依每公斤價值排序並貪婪裝填可證為最佳。0/1 背包看起來幾乎相同——相同物品、相同價值、相同重量、相同容量——只有一個微小改變：每件物品必須整件取或捨棄，不可分割。這單一改變摧毀了貪婪的最佳性，而看清「究竟為何」是這整個領域中關於貪婪何等脆弱最清楚的一課。

完整的失敗如下。容量 50。物品 (價值, 重量)：物品 1 = (60, 10) 密度 6，物品 2 = (100, 20) 密度 5，物品 3 = (120, 30) 密度 4。依密度的貪婪取物品 1（用 10），再取物品 2（用 30），接著試物品 3 但只剩 20 容量而物品 3 重 30——在 0/1 世界裡它不能被切，故完全被排除，得價值 60 + 100 = 160，浪費 20 單位容量。真正的最佳取物品 2 與 3：重量 20 + 30 = 50 恰好填滿袋子，價值 100 + 120 = 220——好得多。貪婪的錯誤是鎖定了高密度但重量尷尬的物品 1，而非完美填滿容量的組合。分數的交換論證失敗，正是因為你不再能換進部分的一公斤來修補次佳的裝法；不可分割性移除了證明所倚賴的那個動作。

結構上，0/1 背包的可行集不構成擬陣——它們違反交換性質——故由擬陣貪婪定理的逆命題，沒有任何基於權重的貪婪規則能普遍最佳。正確方法是動態規劃：在物品與容量上建表，達到 O(n * W) 時間，其中 W 是容量（這是偽多項式的，因為 W 可在輸入位元長度上呈指數，而 0/1 背包一般是 NP 困難；當你能容忍小誤差時，FPTAS 能快速給出近最佳答案）。歷久彌新的結論：0/1 背包是經典的「貪婪看似對卻錯」問題，它的教訓是——表面上與某個貪婪可解問題相似，什麼都不保證；你必須檢查可分割性、交換性質，或構造一個反例。