演算法圖鑑
演算法 · 5 個細項

Greedy貪婪法

貪婪法不回頭、不試錯,只做眼前最好的選擇,所以通常最快。代價是它不一定對:這個主題的重點不只是寫出貪婪解,而是學會用交換論證判斷什麼時候可以貪。

為什麼要學 Greedy

現實中的應用
會議室與課表排程

一堆會議時段,最多能排幾場不衝突?每次選最早結束的那場,這個直覺選法可以被證明是最佳的。

→ 對應課程:Interval Scheduling
zip 與 JPEG 裡的壓縮

常出現的字元給短編碼、少出現的給長編碼。霍夫曼編碼每次合併頻率最低的兩個,貪婪卻是最佳。

→ 對應課程:Huffman Coding
找零與作業系統排程

收銀機從最大面額開始找,作業系統先跑最短的工作。這些策略有的一定對,有的在特定幣值下會錯,差別在哪是這個主題的重點。

→ 對應課程:Coin Change (Greedy)
能不能跳到終點

每格寫著最多能往前跳幾步。只要一直維持「目前最遠能到哪」,掃一遍就知道答案,不必試每條路。

→ 對應課程:Jump Game

細項

5