貪婪何時失敗（when greedy fails）

貪婪很誘人：寫起來短、跑起來快，且常給出看似合理的答案。危險正在於此——貪婪程式幾乎總會回傳「某個東西」，而那東西可能悄悄地、自信地錯。要學的技能是：在信任貪婪之前先懷疑它，在相信它之前先測試它。

每當局部最佳的選擇封死了全域更好的未來——即現在看似最好的選擇犧牲了稍後更有價值的可能性——貪婪就失敗。幾個經典的警訊幫你察覺。第一，不可分割或硬性容量限制：0/1 背包失敗，因為你無法削薄物品來塞入，故密度優先的選擇可能擋住更好的整件組合。第二，目標跨選擇交互作用：任意面額的找零失敗，因為取最大硬幣可能讓你卡在尷尬的餘額。第三，看似合理卻不同的貪婪規則彼此矛盾：若「最短優先」「最早結束」「衝突最少」聽起來都合理卻給出不同答案，至多一個能最佳，故無證明下都不可信。實務防禦有兩面：試著構造一個小反例（常常三四件物品就夠了——0/1 背包，容量 50，物品 (價值 60, 重量 10)、(價值 100, 重量 20)、(價值 120, 重量 30)，依密度的貪婪取前兩件得價值 160，但最佳取後兩件得價值 220），並試著構造一個證明（交換或領先，或擬陣）。若兩者都不成功，就別出貨那個貪婪。

要尊重此事的最深層原因：貪婪的正確性在問題的微小改變下很脆弱。分數背包到 0/1 背包、單房間排程到找零、最小生成樹到旅行推銷員——每一對表面形式幾乎相同卻有相反的貪婪結論，僅由一個假設分隔（可分割性、結構、擬陣性質）。當貪婪失敗時，標準的救援是：若問題具有最佳子結構與重疊子問題就用動態規劃，若它是 NP 困難就用近似演算法。本條目的重點不是背一張清單，而是建立反射：一個「看起來對」的貪婪在背後有反例搜尋、前方有證明之前，什麼都還沒掙得。