1什麼是貪心策略
貪心（Greedy）是你接觸的第一個「演算法策略」，而不是單一個技巧。它的想法很簡單：每一步都選當下看起來最好的選擇，不去考慮這個選擇會不會影響到後面。買東西優先買便宜的、找零錢優先用大面額——這些都是你生活中本來就會的直覺，貪心演算法就是把這個直覺寫成程式。
貪心最重要的觀念，也是它跟你之前學的技巧最不一樣的地方：貪心不是每次都對。它只在某些問題的結構下才能保證「每一步選最好的，最後加起來也是最好的」。這門課選的題目都是貪心策略成立的情境，但你以後遇到新問題時，要先想一下「這一步選當下最好的，會不會反而讓後面沒辦法選到更好的結果」——這正是貪心策略在資訊科學裡最核心的思考方式：不是先寫程式，而是先驗證這個策略講不講得通。
2核心概念，依課程題目的順序拆解
1
暖身——貪心其實常常只是「除法」
有些貪心問題簡單到就是一次整數除法：「已經沒辦法再更好」的答案，本身就是除法的商或無條件進位。
最多可買幾瓶水（GREEDY01-002）：錢÷單價最少箱子數（GREEDY01-006）：物品數÷容量，無條件進位補到目標分數（GREEDY01-007）
⚠️ 常見誤區
忘記「無條件進位」——除得盡才剛好，除不盡的餘數還是需要再多一個箱子/多一題。2
硬幣找零——每次都用最大面額
你要做的事：用 50、10、5、1 元硬幣找零，要用最少硬幣數。貪心策略：每一步都盡量先用最大的面額，用到不能再用（再用下去會超過金額）才換下一級面額。
最少硬幣數（GREEDY01-001）
| 面額組合 | 湊6元的貪心結果 | 其實更好的湊法 |
|---|---|---|
| 1、3、4（貪心會出錯） | 4+1+1（3枚） | 3+3（2枚，更少！） |
| 50、10、5、1（本課使用） | 貪心保證正確 | — |
🆕 補充圖解：貪心不是萬用的——換一組面額，貪心給的答案可能不是最優解新增
這是理解「貪心不一定永遠對」的好例子：50/10/5/1這組面額剛好每一級都是下一級的倍數關係，貪心才會保證正確；如果面額換成例如「1、3、4」，湊6元時貪心會先選4再選1再選1（共3枚），但其實3+3只要2枚更好。這門課的面額都是貪心成立的情況，但記得貪心不是萬用的，要先確認題目的數字結構允不允許。
3
排序後貪心——先排好順序，再依序選
這是貪心策略最常見的套路：先把資料按某個標準排序，再照排好的順序依序做選擇。排序的標準會依題目目標而不同：
- 「優先完成短任務」（GREEDY01-003）：時間由短到長排序，依序做，直到可用時間用完為止——先做短的，才能塞進最多任務
- 「買最多便宜商品」（GREEDY01-004）：價格由低到高排序，依序買，直到預算用完——先買便宜的，才能買到最多件
- 「最大總分選擇」（GREEDY01-005）：分數由高到低排序，取前K個加總——要總分最大，當然優先選分數最高的
- 「最多裝入背包」（GREEDY01-008）：重量由輕到重排序，依序裝，直到裝不下為止——想裝最多「件數」，優先選輕的才塞得下更多件
⚠️ 常見誤區
排序方向選反了——想要「最多件數」通常要由小到大排序（先滿足最容易滿足的），想要「總值最大」通常要由大到小排序（優先拿貢獻最大的）。做每一題前先問自己：「我要的是數量最多，還是總值最大？」這會決定排序方向。4
排序後貪心的進階應用
M2-10 的多數題目都是概念3「排序後依序選」套用在更複雜的情境上：
- 「簽唱會門票」（115J-02）：粉絲依積分排序，取前K名（跟「最大總分選擇」是同一招）
- 「圖書館的舊書打包」（cycjunior-003）：書本已經由重到輕排好，依序裝箱，裝不下就換下一箱
- 「購買紀念品」（TYTN-12）：在預算內盡量買到最多件紀念品——概念3的變形，多了「商品數量有限」的條件
5
配對型貪心——把兩端排序後配對
你要做的事（大隊接力的棒次安排，cyjunior-004）：把一群人依能力值排序後，用某種配對規則（例如強的跟弱的配對）安排順序。這種「排序後從兩端各取一個」的貪心，常出現在「盡量拉近差距」或「平衡負擔」類的題目——「星際物資運補-疏散飛船的乘客名單」（nantoJS-006-2，體重限制下配對乘客）也是同樣的思路：清單已經由小到大排好，同時用兩個指標，一個從最重的開始、一個從最輕的開始，往中間逼近做配對。
6
固定順序的模擬——不是「選」而是「照順序處理」
「可口便當」（WP-06）不是要你「挑」出最好的組合，而是給定一個已經決定好的處理順序，要你照這個順序把訂單重新排列輸出。這一題提醒你：不是所有跟「順序」有關的題目都是貪心——有些只是單純的模擬，先看清楚題目要的是「你自己決定最佳策略」還是「照題目給的規則模擬」。
7
更多進階應用（可依需要挑戰）
M2-10 還有幾題把貪心結合更複雜的情境包裝：「星際物資運補-神祕的配重」「星際物資運補-火星樣本回收」（重量/價值比的取捨）、「超市採購即時通」「金門小三通春運調度」「王牌教練」「金門粥糜採購任務」「外送員的接單策略」「神秘的煉金術配對」。這些題目沒有新的核心概念，是概念3～5的實戰演練，建議前面的概念都熟悉、也能說出「為什麼這樣排序」之後再挑戰。
3建議練習順序對照表
| 順序 | 概念 | 題目 | 課程 |
|---|---|---|---|
| 1 | 除法型貪心 | 最多可買幾瓶水／最少箱子數／補到目標分數 | M2-09 |
| 2 | 硬幣找零（貪心的界線） | 最少硬幣數（GREEDY01-001） | M2-09 |
| 3 | 排序後貪心：時間 | 優先完成短任務（GREEDY01-003） | M2-09 |
| 4 | 排序後貪心：花費 | 買最多便宜商品（GREEDY01-004） | M2-09 |
| 5 | 排序後貪心：總分 | 最大總分選擇（GREEDY01-005） | M2-09 |
| 6 | 排序後貪心：件數 | 最多裝入背包（GREEDY01-008） | M2-09 |
| 7 | 進階排序貪心 | 簽唱會門票／圖書館的舊書打包／購買紀念品 | M2-10 |
| 8 | 配對型貪心 | 大隊接力的棒次安排／星際物資運補-疏散飛船的乘客名單 | M2-10 |
| 9 | 固定順序模擬（辨析用） | 可口便當 | M2-10 |
| 10 | 綜合進階應用 | 超市採購即時通／金門小三通春運調度／王牌教練等 | M2-10 |
🆕 本頁新增內容說明
以下視覺元素為 Cowork 潤飾時新增，MD 正本中沒有：① 貪心「不是萬用」的面額對照表（把MD原本的文字敘述改成表格呈現，內容相同）。若確認保留，建議之後補進 MD 正本。