想象一下，你去商店買東西，老闆找你1元7角零錢。你猜老闆會怎麼給你？通常他會先給你1個1元硬幣（如果有的話），然後是5角，再是1角，儘量用最少的硬幣湊夠金額。這種“每次都選當前最好的選擇，不管未來”的思路，其實就是貪心算法的核心思想。
什麼是貪心算法？¶
貪心算法（Greedy Algorithm）是一種在每一步選擇中都採取當前狀態下最優的選擇（即局部最優解），並希望通過一系列局部最優選擇最終得到全局最優解的算法。
簡單來說，它就像一個“短視”的決策者：只看眼前的好處，不考慮長遠影響。這種策略的關鍵在於，問題是否滿足“貪心選擇性質”——即每一步的局部最優選擇，最終能導致全局最優。如果滿足，貪心算法就能高效解決問題；如果不滿足，可能會得到非最優解。
找零錢問題：貪心算法的經典應用¶
找零錢問題是貪心算法最經典的例子。假設我們有以下幾種硬幣（面額）：25分（quarter）、10分（dime）、5分（nickel）、1分（penny）。現在要找給顧客67分，如何用最少的硬幣數量湊齊？
問題分析¶
目標：用最少的硬幣湊出67分。
核心思路：從最大面額開始，每次取儘可能多的當前面額，直到金額爲0。這種策略在硬幣面額滿足“任意大面額都不能被更小面額組合出”的情況下（比如25、10、5、1），能保證局部最優，進而全局最優。
具體步驟（以67分爲例）¶
- 確定硬幣面額：假設硬幣按從大到小排序爲
[25, 10, 5, 1]。 -
從最大面額開始計算：
- 25分硬幣：67 ÷ 25 = 2（最多取2個），2×25=50分，剩餘金額：67 - 50 = 17分。
- 10分硬幣：17 ÷ 10 = 1（最多取1個），1×10=10分，剩餘金額：17 - 10 = 7分。
- 5分硬幣：7 ÷ 5 = 1（最多取1個），1×5=5分，剩餘金額：7 - 5 = 2分。
- 1分硬幣：2 ÷ 1 = 2（最多取2個），2×1=2分，剩餘金額：0分。 -
統計總硬幣數：2（25分）+ 1（10分）+ 1（5分）+ 2（1分）= 6枚。
驗證最優性¶
有沒有更少的組合？比如“50分+10分+5分+2分1分”，同樣是6枚硬幣，沒有更少的了。這說明貪心算法在這裏確實得到了最優解。
貪心算法的侷限性¶
貪心算法並非萬能。如果硬幣面額不滿足“局部最優能推全局最優”，可能會失效。例如：
- 硬幣面額：[1, 3, 4]（假設沒有2分硬幣），目標金額6分。
- 貪心策略：先取4分，剩餘2分，取1分×2，共3枚硬幣。
- 最優解：取3分×2，共2枚硬幣。
這裏貪心算法失敗了，因爲局部最優（取4分）反而導致全局更差。因此，貪心算法只適用於滿足“貪心選擇性質”的問題——即每一步選擇最大面額後，剩下的子問題與整體問題結構相同。
貪心算法的適用場景¶
找零錢問題中，只要硬幣面額滿足“任意大面額都大於等於所有小面額之和”（比如25、10、5、1，其中10+5+1=16 < 25，5+1=6 < 10，1 <5），貪心就能高效解決。
類似場景還有：
- 活動安排：選擇最多不重疊的會議（按結束時間排序，每次選最早結束的活動）。
- 哈夫曼編碼：構建最優前綴碼（優先合併頻率最小的節點）。
總結¶
貪心算法的核心是“局部最優→全局最優”，簡單直觀，在合適的問題上效率極高。找零錢問題中，只要硬幣面額合理，貪心算法能快速得到最少硬幣數量。但需注意：貪心算法不保證所有問題都能得到最優解，僅適用於滿足貪心選擇性質的問題。
下次你遇到“如何用最少步驟完成任務”時，不妨試試貪心思想——從最大面額（或最優起點）開始，每一步選當前最好的選擇，說不定就能高效解決問題！