1. 什么是貪心算法？

貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是全局最好或最優的算法。

核心思想：“每步都貪心地選擇眼前最好的，不去考慮整個未來的長遠情況”。

它就像我們生活中“只顧眼前利益”的決策方式。例如，在找零錢時，為了湊出某個金額，我們總是先給出最大面額的鈔票，然后再給更小的，這就是一種貪心思想。

2. 貪心算法的基本要素

一個問題是適用于貪心算法，通常需要具備兩個重要的性質：

1. 貪心選擇性質

   • 定義：一個問題的全局最優解可以通過一系列局部最優的選擇（即貪心選擇）來達到。
   • 解釋：這是貪心算法可行的前提。它要求我們在做貪心選擇時，不會影響子問題的解。也就是說，我們做完一次選擇后，只需要解決一個更小的子問題，而不需要回頭重新考慮之前的選擇。

2. 最優子結構

   • 定義：一個問題的最優解包含其子問題的最優解。
   • 解釋：這是動態規劃和貪心算法都具備的性質。如果整個問題的最優解可以由各個子問題的最優解推導出來，那么我們就說這個問題具有最優子結構。

簡單來說：貪心算法在每一步做出一個不可撤回的決策，并且希望每一步的局部最優能最終堆砌出全局最優。

3. 貪心算法的基本步驟

1. 建立數學模型：將問題抽象為一個數學決策模型。
2. 分解問題：將待求解的問題分解成若干個子問題。
3. 制定貪心策略：根據題意，選擇一個貪心準則，決定如何做出當前的最優選擇。這是貪心算法的核心和難點。
4. 求解子問題：根據貪心策略，一步步得到子問題的局部最優解。
5. 組合成最終解：將所有的局部最優解組合成原問題的一個解。

4. 經典示例

示例1：找零錢問題

問題：假設硬幣體系是 1元、5角、1角、5分、1分。現在要找給顧客 1元8角6分，如何找零才能使找零的硬幣個數最少？

貪心策略：每一步都使用當前可用的最大面額的硬幣。

步驟：

1. 1元8角6分 = 186分
2. 先找 1元（100分），剩余 86分。
3. 找不了1元了，找 5角（50分），剩余 36分。
4. 找不了5角了，找 1角（10分），可以找3個，剩余 6分。
5. 找 5分（5分），剩余 1分。
6. 找 1分（1分），完成。

找零方案為：1個1元，1個5角，3個1角，1個5分，1個1分。總共 7 枚硬幣。

為什么這是有效的？ 在這個特定的硬幣體系（ canonical coin systems ）中，貪心算法總能得到最優解。但注意，如果硬幣體系很奇怪（例如有 1分, 3分, 4分），要湊出 6分：

• 貪心法：先拿4分，剩余2分，再拿兩個1分，共3枚硬幣（4，1，1）。
• 最優解：其實是兩個3分，共2枚硬幣（3，3）。
  所以，貪心算法并不總是能得到最優解！

示例2：活動選擇問題

問題：有一系列活動，每個活動有開始時間和結束時間。同一時間只能進行一個活動。如何選擇才能使能進行的活動數量最多？

貪心策略：每次都選擇結束時間最早的活動，這樣就能為后續活動留下更多的時間。

步驟：

1. 將所有活動按結束時間從早到晚排序。
2. 選擇第一個結束的活動。
3. 接下來，選擇開始時間晚于或等于上一個已選活動結束時間的活動中，結束時間最早的那個。
4. 重復步驟3，直到沒有活動可選。

這個策略被證明總能得到最優解。

5. 貪心算法 vs 動態規劃

這是一個常見的困惑點，因為它們都用于求解優化問題且都具有最優子結構性質。

特性	貪心算法	動態規劃
決策方式	每步做一個不可撤回的決策，不考慮未來。	每步決策依賴于子問題的解，需要保存所有子問題的解并根據這些解做出決策。
子問題	做出一次貪心選擇后，只產生一個子問題。	通常會產生多個重疊子問題。
效率	高效，通常時間復雜度更低。	相對較低，因為需要解決所有子問題。
適用范圍	要求問題具有貪心選擇性質。	適用范圍更廣，只要具有最優子結構（即使沒有貪心選擇性質）。
結果	不一定得到全局最優解。	總是得到全局最優解。

關鍵區別：動態規劃在做出決策時，需要考慮所有可能的選擇（通常通過比較得出）；而貪心算法則直接做出一個“看似最好”的選擇，并且不再回頭。

6. 貪心算法的優缺點

優點：

• 高效：算法通常簡單、直接，時間復雜度低。
• 易于實現：邏輯清晰，代碼通常不長。

缺點：

• 局部最優不等于全局最優：這是最大的陷阱。很多問題無法用貪心算法得到真正的最優解。
• 證明困難：如何證明一個貪心策略一定能得到全局最優解，通常是比較困難的。

7. 如何判斷能否使用貪心算法？

這是一個沒有萬能公式的問題，但可以遵循以下思路：

1. 先嘗試：先想一個貪心策略，然后用一些簡單的測試用例（尤其是邊界 case）去驗證它是否能得到最優解。
2. 舉反例：嘗試思考是否存在一種情況，讓你的貪心策略會做出錯誤的選擇。如果能輕易找到反例，則說明貪心算法不適用。
3. 數學證明：嘗試從數學上證明該問題具有貪心選擇性質和最優子結構。這需要較強的數學功底，也是算法競賽和研究的重點。

總結

貪心算法是一種強大而直觀的“短視”算法。它通過一系列局部最優決策來構建解，期望最終得到全局最優解。

• 核心：制定正確的貪心策略。
• 關鍵：問題必須具有貪心選擇性質和最優子結構。
• 陷阱：局部最優不一定是全局最優。
• 對比：與動態規劃相比，它更高效但不總是最優；動態規劃更通用但更耗時。

掌握貪心算法需要大量的練習，去熟悉各種經典問題（如霍夫曼編碼、最小生成樹-Prim和Kruskal算法、單源最短路徑-Dijkstra算法等）的貪心策略。