貪心演算法原理#

貪心演算法（Greedy Algorithm）的核心定義：在對問題求解時，總是做出在當前看來最好的選擇。

核心概念#

貪心演算法追求「局部最優解（Local Optimal）」，期望透過無數次的局部最優，最終推導出「全域最優解（Global Optimal）」。

經典案例：湊零錢#

案例 A：貪心成功#

湊出 36 元，可用面額：20、10、5、1 元

貪心策略：優先選最大面額

  1. 取 1 張 20 元（剩 16 元）
  2. 取 1 張 10 元（剩 6 元）
  3. 取 1 張 5 元（剩 1 元）
  4. 取 1 張 1 元（剛好）

結果：4 張 - 這是最優解

案例 B：貪心失敗#

湊出 18 元，可用面額：10、9、1 元

貪心策略：

  1. 取 1 張 10 元（剩 8 元）
  2. 8 元只能用 8 張 1 元
  3. 結果：9 張

實際最優解： 2 張 9 元 = 2 張

此案例展示了貪心的陷阱：第一步貪心選擇 10 元，就註定無法達到最優。

適用條件#

判斷是否該使用貪心演算法：

  1. 可拆解為子問題 - 問題能分解成若干子問題
  2. 最佳子結構（Optimal Substructure） - 子問題的最優解能推導出原問題的最優解

在面試中，純粹考貪心的題目相對較少。原因是它能解決的問題有限，且往往需要嚴格的數學證明。如果發現貪心行不通，應轉向考慮動態規劃。

貪心 vs 動態規劃#

特性貪心演算法動態規劃
決策模式每步選當前最優，不可回退記錄多種可能，可回溯
狀態儲存只保留當前最優解儲存所有中間結果
結果保證可能陷入局部最優保證全域最優
計算效率快相對較慢
擬人化比喻

貪心演算法：像一條路走到黑的人，只看腳下，不回頭。

動態規劃：像步步為營的策略家，同時記錄多條路徑的代價，最後選總代價最小的那條路。

常見的貪心問題#

  • 區間調度問題
  • 霍夫曼編碼
  • 最小生成樹（Prim、Kruskal）
  • 單源最短路徑（Dijkstra）
  • 股票買賣（無限次交易）
Backward 貪心演算法 貪心演算法應用 Forward