上一篇，我們用找零錢的問題認識了 Greedy。
假設要找 67 元，可以使用 50、10、5、1 的面額。
當我們每一步都選擇：

不超過剩餘金額的最大面額

會得到：

67 → 選 50
17 → 選 10
 7 → 選 5
 2 → 選 1
 1 → 選 1

最後：

50 + 10 + 5 + 1 + 1

一共使用 5 枚硬幣。

這個策略非常合理，而且在這組硬幣裡，看起來也真的很好用。
於是我們可能很快得到一個直覺：

每一步都選現在最好的選項，最後應該就會得到最好的答案

但事情真的永遠都是這樣嗎？

今天我們只要換掉硬幣的面額，這個直覺就會立刻出問題。

換一組硬幣看看

假設現在可以使用的硬幣變成：

1、3、4

我們要找 6 元。
目標也沒有改變：

使用最少的硬幣湊出 6

如果沿用上一篇的 Greedy 策略：

每次選擇不超過剩餘金額的最大面額

第一步面對：

剩下 6

可以選：

1、3、4

最大的是 4，所以我們選 4。
現在剩下：

2

但 3 和 4 都已經不能用了，只好選 1。
剩下：

1

再選一次 1。
最後得到：

4 + 1 + 1 = 6

總共用了 3 枚硬幣。
我們確實成功找出了一個答案。
但如果不要急著在第一步選 4 呢？

其實還有另一個明顯的組合：

3 + 3 = 6

只需要 2 枚硬幣。

於是我們發現：

Greedy：
4 + 1 + 1
→ 3 枚

更好的答案：
3 + 3
→ 2 枚

Greedy 確實找到了一個可行答案，但它沒有找到最好的答案。

問題出在哪裡？

第一步選 4，有錯嗎？
如果我們只看第一步，其實完全沒有。
當時的狀態是剩下 6。
可選的硬幣有：

1、3、4

如果我們的規則是：

選擇現在能拿的最大硬幣

那 4 當然就是最合理的選擇。
也就是說：

4 是這一步看起來最好的選擇

這種只根據目前狀態判斷出的最佳選擇，可以理解成：

局部最佳（local optimum）

但我們真正想解的問題不是：

第一枚硬幣要拿多大？

而是：

整個找零過程總共要使用多少枚硬幣？

所以真正重要的是最後完整答案的品質。

也就是：

整體最佳（global optimum）

在這個例子裡第一步選 4看起來很完美。

但它最後把我們帶到：

4 + 1 + 1

而第一步選 3，雖然第一眼不像是在拿最大的硬幣，最後卻得到：

3 + 3

這明顯是更好的完整答案。
這就是 Greedy 最核心的風險：

局部最優不一定會導向全域最優

Greedy 真正做的是「現在就決定」

Greedy 有一個非常重要的特徵：

做出選擇之後，通常就不回頭重新考慮

例如剛才第一步選了 4 後面就從剩下 2繼續處理。

Greedy 不會走到最後突然說：

等等。

如果剛剛不要拿 4，
改拿 3 會不會更好？

如果我們真的開始這樣做，就已經不只是單純的 Greedy 了。
我們開始嘗試：

• 選 4 會怎樣？
• 選 3 又會怎樣？

也開始比較不同選擇產生的後續結果。
而 Greedy 的特點正好就在於：

它不想把所有可能都試一遍

它希望每一步做出一個看起來最好的決定，然後繼續往前。
這讓 Greedy 常常非常直覺，而且實作也可能很簡單。

但代價就是：

你必須確定「現在看起來最好」真的不會害到後面的答案

為什麼上一篇的硬幣卻沒問題？

這時可能會出現一個疑問。
上一篇我們面額是：

50、10、5、1

Greedy 明明運作得很好。
今天只是換成：

4、3、1

為什麼突然就失敗了？

兩邊使用的規則其實完全一樣：

每次拿不超過剩餘金額的最大硬幣

真正改變的是：

問題本身的結構

有些硬幣系統中，大面額與小面額之間的關係，剛好讓這個 Greedy 策略可以得到最佳解。
但並不是任意設計一組面額，都會具備這種性質。
面額 1、3、4，就是一個很簡單的反例。

所以 Greedy 很合理跟 Greedy 一定正確，其實是完全不同的兩件事，不該混為一談。

「這個策略很直覺」不是 correctness proof

這也是演算法裡很重要的一個觀念。
我們很容易說：

先拿最大的不是很合理嗎？
每次都做現在最好的選擇，最後應該不會太差吧？

這些都可以幫助我們產生演算法，但它們不能證明演算法是正確的。
因為演算法真正需要回答的是：

對所有符合條件的輸入，這個策略都能得到我們承諾的結果嗎？

只要找到一個反例：

硬幣：1、3、4
金額：6

Greedy：

4 + 1 + 1

最佳答案：

3 + 3

我們就知道：

「永遠選最大硬幣」不是一般找零問題的正確最佳化演算法

它可能在很多情況表現很好。
可能在某些特定硬幣系統永遠正確。
但我們不能因為它「看起來合理」，就直接把它當成所有情況都成立的規則。

那怎麼找出真正的最少硬幣？

對目前這個問題，如果硬幣面額都是正整數、每種硬幣都可以重複使用，而且目標金額不大，我們可以使用動態規劃（Dynamic Programming，DP）。

它不會只保留當下選中的硬幣，而是記住：

dp[x] = 湊出金額 x 最少需要幾枚硬幣

已知：

dp[0] = 0

因為湊出 0 元不需要任何硬幣。
其他位置一開始可以設成 Infinity，表示目前還不知道該怎麼湊出這個金額。
計算其他金額時，我們可以嘗試每一種放得進去的硬幣：

dp[x] = min(dp[x - coin] + 1)

以面額 1、3、4 為例，最後會得到：

x       0  1  2  3  4  5  6
dp[x]   0  1  2  1  1  2  2

計算 dp[6] 時，實際比較的是：

選 1 → dp[5] + 1 = 3
選 3 → dp[3] + 1 = 2
選 4 → dp[2] + 1 = 3

最小值是 2，因此湊出 6 元最少需要兩枚硬幣。
如果除了數量，也想知道實際選了哪些硬幣，可以在更新 dp 時順便記住這次的選擇：

function findMinCoins(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  const choice = Array(amount + 1).fill(null);

  dp[0] = 0;

  for (let current = 1; current <= amount; current += 1) {
    for (const coin of coins) {
      if (coin > current) continue;

      const candidate = dp[current - coin] + 1;

      if (candidate < dp[current]) {
        dp[current] = candidate;
        choice[current] = coin;
      }
    }
  }

  if (!Number.isFinite(dp[amount])) return null;

  const usedCoins = [];

  for (let current = amount; current > 0; current -= choice[current]) {
    usedCoins.push(choice[current]);
  }

  return {
    count: dp[amount],
    coins: usedCoins,
  };
}

console.log(findMinCoins([1, 3, 4], 6));
// { count: 2, coins: [3, 3] }

假設目標金額是 amount，硬幣有 n 種，這個解法的時間複雜度是 O(amount × n)，空間複雜度是 O(amount)。

DP 並不是因為「每一步選得更聰明」，而是利用較小金額的最佳答案，完整比較不同選擇可能帶來的結果。
這也讓我們看見另一種解題方向，但本篇真正要追問的仍然是：

什麼情況下 Greedy 才能安全地省略這些比較？

Greedy 要成立，問題本身必須允許它

我們在決定使用 Greedy 之前，該思考的是：

這個問題能不能安全地使用 Greedy？

某些問題具有一種很重要的性質：

做出某個局部最佳選擇之後，仍然存在一個整體最佳解法包含這個選擇

這通常被稱為：

Greedy-choice property

直覺上可以理解成：

我現在選這個最好選項
        ↓
不會因此把真正的最佳答案排除掉
        ↓
剩下的問題繼續用相同方式處理

如果問題具有這種結構，Greedy 才有機會每一步都做出眼前看起來最好的選擇，最後仍然得到整體最佳。
反過來說，如果第一步的選擇可能破壞後面的組合：

現在拿 4 看起來很好
        ↓
卻讓剩下的 2 只能拆成 1 + 1
        ↓
錯過 3 + 3

那我們就不能只因為某個選項現在最好，就認為它一定屬於最佳答案。

局部最佳和整體最佳，是兩個不同問題

我們可以把今天的差異整理成：

• 局部最佳 → 目前這一步看起來最好
• 整體最佳 → 整個答案完成之後最好

Greedy 做的事情通常是：

局部最佳
→ 局部最佳
→ 局部最佳
→ 局部最佳

它希望最後自然得到整體最佳。

但這個箭頭：

一連串局部最佳
        ↓
整體最佳

並不是天經地義，它必須依賴問題本身具有某些特定前提。
這也是為什麼學 Greedy 時，真正困難的是去反思：

你憑什麼知道眼前這一步的選擇，不會破壞整體最佳？

找到一個答案，和找到最佳答案並不一樣

今天這個例子還讓我們看到另一個容易混淆的地方。
Greedy 得到 4 + 1 + 1 這並不是錯誤答案。
因為 4 + 1 + 1 = 6 它確實成功完成找零。

所以如果問題只是：

能不能湊出 6？

那它已經完成任務了。
但我們上一篇設定的最佳化目標是：

使用最少的硬幣

一旦加入這個目標，問題就不再只是問可行性問題，還包含著哪個解決方案最好？
也就是說：

可行答案：
4 + 1 + 1

可行答案：
3 + 1 + 1 + 1

可行答案：
3 + 3

...

最佳化目標：
最小化硬幣數量

因此 4 + 1 + 1 雖然是一種解法，卻不是最優解。
這個差異在後面的最佳化問題裡會越來越重要。

演算法不是靠感覺合理就一定正確

Greedy 很容易讓人產生一種錯覺：

我每一步都沒有做錯，最後怎麼可能錯？

但問題就在於：

「每一步單獨看起來合理」與「所有步驟組合起來最佳」不是同一件事

尤其當現在的選擇會影響未來還剩下哪些選擇時，事情就開始變得困難。
今天選了 4，不只代表我們得到一枚 4 元硬幣。
也代表我們把問題改成：

剩下 2

而這個新的狀態，決定了後面還能怎麼組合。
所以每一次的決定都不只是：

我現在拿到了什麼？

同時也是：

我因此放棄了哪些未來可能？

這也是很多最佳化問題真正困難的地方。

從當下選擇走向整體組合

透過硬幣的反例，我們看到了 Greedy 最需要小心的地方：

局部最佳 ≠ 整體最佳

Greedy 能不能得到最佳答案，不是看策略聽起來是否合理，而是取決於：

問題本身是否允許我們選擇眼前最佳，又不會因此排除整體最佳解

硬幣只是很小的例子。
如果每個選項不只帶來不同價值，也會占用不同大小的空間，選擇就會變得更複雜：

• 每個物品有不同價值
• 每個物品有不同重量
• 可以使用的容量有限

這時，選下一個「看起來最好」的物品，不只會得到它的價值，也會減少其他物品可以使用的空間。

問題因此從哪一個物品最好？
轉向成：

哪些物品放在一起，才是更好的整體組合？

下一篇，我們就從一個容量有限的行李箱開始，看看這類問題為什麼不能只比較單一物品。

當價值、重量與容量同時存在時，我們應該怎麼決定要帶走哪些東西？