演算法設計範式
貪婪演算法
貪婪演算法一步一步地搭建解，並且在每一步都抓住此刻看起來最好的那個——局部最優的選擇——而且從不回頭反悔。想像給顧客找零、手裡有一把硬幣：你先遞出仍然裝得下的最大面額，再對剩下的金額遞出裝得下的最大面額，如此往復。這是最簡單、最自然的策略，一旦它管用就快得出奇，往往排序之後只需掃一遍。
陷阱在於——而且是個大陷阱——此刻的最佳選擇，未必是整體最佳方案的一部分。貪婪只有在問題具備一種特殊性質時才正確：做出局部最優的選擇永遠不會斷送通往全域最優答案的路（常稱作貪婪選擇性質，與最優子結構並列）。在日常的美元/歐元幣制下，「拿最大面額的硬幣」總能給出最少枚數。但若自造一套幣值為 {1, 3, 4} 的硬幣去湊 6：貪婪會先拿 4、再拿 1、再拿 1——三枚——而真正的最優是 3 + 3，只要兩枚。同一個演算法，換了資料，答案就錯。
因此貪婪設計講究的是證明，而不只是「看起來對」：你必須論證這個貪婪選擇是安全的，或者找到一個反例把它推翻。在那些確實成立的地方，貪婪是首選方法——霍夫曼編碼透過反覆合併出現頻率最低的兩個符號來構造最優前綴碼；Dijkstra 最短路徑與標準的最小生成樹演算法（Kruskal、Prim）骨子裡都是貪婪。當貪婪失效時，通常的救兵是動態規劃，它會權衡更多選項，而不是一看到順眼的就立刻定下。
// Greedy change: always take the largest coin that fits.
int greedyCount(vector<int> coins, int amount) {
sort(coins.rbegin(), coins.rend());
int n = 0;
for (int c : coins)
while (amount >= c) { amount -= c; ++n; }
return n; // correct ONLY if the coin system is canonical
}面值 {1,3,4}、金額 6 時，貪婪給出 4+1+1（3 枚）；最優是 3+3（2 枚）。
貪婪與動態規劃很容易混淆：兩者都需要最優子結構，但貪婪在每一步只認定一個選擇、絕不回頭，而動態規劃會保留若干候選答案、讓表格來定奪。如果你沒法證明貪婪的選擇是安全的，就轉用動態規劃。
又稱
另見