貪婪演算法總是選擇當下看起來最優的方案，並且從不回頭反悔。當它適用時，便是競賽程式設計中最簡單、最快速的工具之一。
對於備戰 USACO（USA Computing Olympiad）等奧林匹克競賽的學生來說，貪婪技巧是一道必經的門檻。它首次正式出現在 Silver 級別，參賽者從這裡開始學習諸如遞迴搜尋和貪婪策略等基礎解題模式；而在 Gold 和 Platinum 級別的題目中，貪婪也會與其他思路結合出現。理解何時「每一步都抓取最優選項」才能真正得出全域最優答案，正是區分嚴謹選手與運氣型選手的一項能力。
是什麼讓一個演算法成為「貪婪」？
貪婪演算法逐步建構解決方案，每次都選擇能帶來最直接收益的下一步，而不重新考慮此前的選擇。這與動態規劃不同，後者會探索多種選擇的組合。貪婪更快且佔用更少記憶體，但只有當問題具備恰當結構時，它才能給出正確答案。
兩條性質使貪婪方法成立：
- 貪婪選擇性質：局部最優的選擇總能成為某個全域最優解的一部分。
- 最優子結構：整個問題的最優解包含其子問題的最優解。
若兩者都成立，貪婪便有效。若不成立，貪婪可能得出一個看似合理卻錯誤的答案，而這正是許多初學者在競賽中落入的陷阱。
值得掌握的經典問題
少數幾道教科書式的問題幾乎涵蓋了你在競賽場景中所需的每一種貪婪模式：
- 區間排程（活動選擇）：要選出最多數量的互不重疊區間，可按結束時間排序，然後反覆選取仍能放入的最早結束的區間。先排序是 USACO Silver 中最常見的貪婪套路。
- 分數背包：按價值與重量之比排序，優先選取單位價值最高的物品，必要時分割最後一件物品。注意，物品不能分割的 0/1 版本則需要改用動態規劃。
- Huffman 編碼：反覆合併出現頻率最低的兩個符號以建構最優前綴編碼，這是一種在真實資料壓縮中使用的貪婪方法。
需要記住的模式：大多數競賽貪婪題都以排序開始。問問自己「按什麼關鍵字排序？」——結束時間、比率、截止期限還是大小——其餘的解法往往隨之而來。
證明貪婪是正確的
這正是學生們會跳過的部分，而它會讓他們丟分。貪婪思路必須經過論證，而不能僅僅因為範例通過就提交。最可靠的工具是交換論證。
假設某個最優解與貪婪解不同。找到它們第一處產生分歧的地方，然後證明換入貪婪選擇不會使解變得更差。如此反覆，最優解便能在不損失品質的前提下轉化為貪婪解，因此貪婪也必定是最優的。
其他有用的技巧包括數學歸納法和反證法。即使是簡短的書面論證，也能幫助你在評測系統之前發現反例。當你無法證明正確性時，應將其視為一個警示訊號：貪婪可能是錯誤的工具，需要改用動態規劃或搜尋。
如何練習
- 先用暴力法解決一道題，然後尋找貪婪捷徑並證明兩者結果一致。
- 在編寫程式之前，始終嘗試為自己的貪婪思路建構一個反例。
- 記錄是哪個排序關鍵字攻破了每道題；久而久之，你就能瞬間識別出模式。
USACO 在一個賽季中會舉辦數場比賽，每場都給參賽者數小時的時間窗口，在所屬分組（Bronze、Silver、Gold 或 Platinum）中完成一小組題目。賽制、參賽資格和時間安排可能逐年變化，因此在報名前請查閱官方 USACO 資訊以獲取最新詳情。
貪婪思維獎勵那些審慎推理而非憑空猜測的學生。如果您的孩子喜歡這種結構化的解題方式，BIAA 的競賽程式設計專案將引導有志向的中小學生從第一道「排序加選擇」的題目，一路走向高階的奧林匹克競賽備戰。探索 BIAA，找到合適的起點。