每一步都選當下最好的,不回頭。快又簡單 —— 但只在對的問題上才會是最優解。
每步選當下最好 —— 用一個簡單規則(最大、最近、最便宜…)挑一個選項。
選了就定案 —— 不回頭、不重試,跟回溯 / DP 完全相反。
又快又省 —— 通常 O(n) 或 O(n log n)(常先排序),不用額外的表。
風險:可能只是「局部最好」 —— 一連串局部最好,不保證加起來是全域最好。
貪婪選擇性質 —— 每一步的局部最優選擇,一定能通往全域最優(需要證明,不能只是感覺對)。
最佳子結構 —— 做完這步後,剩下的子問題結構一樣。
有效的例子 —— 活動選擇、Huffman 編碼、Dijkstra、最小生成樹、找零(canonical 面額)。
失敗的例子 —— 0/1 背包、亂七八糟面額的找零 —— 這些要用 DP。
貪婪 —— 選一個當下最好的,不回頭。快,但只在特定問題正確。
DP —— 考慮所有選擇、記下子答案。慢一點,但保證最優。
怎麼選 —— 先想貪婪行不行(能證明就用,最快);不確定或有反例,就用 DP。
下面視覺化就示範 —— 同樣是找零,一組面額貪婪剛好最省,換一組就失敗。
找錢時先給最大面額,一路往下,通常張數最少(台幣面額剛好成立)。
每步都選最陡的上坡,可能只爬到旁邊的小山頭(局部最高),而不是真正的最高峰。
先抓當下 CP 值最高的、不回頭 —— 快,但未必湊出整體最划算的組合。
貪婪找零:每一步都拿「≤ 剩餘金額的最大面額」。紫框是這步選的面額。切換兩個情境看差別 —— 台幣面額貪婪剛好最省;換成 [1, 3, 4] 湊 6,貪婪就不是最省了。按「下一步」。
從貪婪找零(含失敗反例)、活動選擇、跳躍遊戲、加油站,到 Huffman、分數背包,以及貪婪失敗要改 DP 的例子。
❌ 沒證明就用貪婪 —— 它常「看起來對」,小測資都過,特定測資才錯。用前最好證明或找反例。
❌ 排序沒選對關鍵 —— 貪婪常靠「依某個值排序」;排錯欄位(結束時間 vs 開始時間)答案全歪。
❌ 把貪婪用在該用 DP 的題 —— 0/1 背包、亂面額找零,貪婪會給次優解。
❌ 選了又想反悔 —— 那就不是貪婪了(是回溯 / DP)。貪婪的前提就是不回頭。
[1,5,10,50] 湊 68 元貪婪拿哪幾枚、共幾枚?換成 [1,3,4] 湊 6,貪婪拿幾枚?最省又是幾枚?把答案打到對話裡,我幫你對。