tags: `ADA 7.3`

ADA 7.3: Coin Changing 找零錢問題

Greedy #2: Coin Changing

Textbook Exercise 16.1

Coin Changing Problem

題目解說

Input: n dollars and unlimited coins with values
${v_{i}} (1, 5, 10, 50)$
- 輸入 n 塊錢和
  ${v_{i}} (1, 5, 10, 50)$ 每種幣值都無限的
Output: the minimum number of coins with the total value n
- 如何用最少的硬幣湊出 n
Cashier’s algorithm: at each iteration, add the coin with the largest value no more than the current total
從最大但不超過現在金額的幣值開始給，例如 n = 46
- 店員會找你 4 個 10 元
- 剩下 6 元找給你，1 個 5 元
- 剩下 1 元找給你，1 個 1 元

💡 用這個方法就可以拿到 OPT 嗎？要怎麼證明呢？

Step 1: Cast Optimization Problem

💡 Coin Changing Problem
Input: n dollars and unlimited coins with values

{v_{i}} (1, 5, 10, 50)

Output: the minimum number of coins with the total value n

先分析出我們的 Subproblem

Subproblems
- C(i): 湊出金額 i 需要的最小的硬幣數量
- 目標: 得到 C(n)

Step 2: Prove Optimal Substructure

如何證明 Optimal Substructure ?

假設 OPT 是 C(i) 的一個 optimal solution，有以下四種情況(四種幣值)：
- Case 1: 第一個硬幣在 OPT 裡面
  - 把第一個硬幣從 OPT 裡面拿掉的話，他就一定會是 i 減掉第一個硬幣的金額的 optimal solution →
    $c (i - v_{1})$
  - 證明：如果存在一個更好的 solution 可以湊出
    $c (i - v_{1})$ ，這樣就可以用這個更好的 solution 配上第一個硬幣，就會得到一個更好的 C(i)，這件事情就矛盾了，所以這件事情必定成立。
- Case 2: 第二個硬幣在 OPT 裡面
  - 把第二個硬幣從 OPT 裡面拿掉的話，他就一定會是 i 減掉第二個硬幣的 value 的 optimal solution →
    $c (i - v_{2})$
- Case 3: 第三個硬幣在 OPT 裡面
  - 把第三個硬幣從 OPT 裡面拿掉的話，他就一定會是 i 減掉第三個硬幣的 value 的 optimal solution →
    $c (i - v_{3})$
- Case 4: 第四個硬幣在 OPT 裡面
  - 把第四個硬幣從 OPT 裡面拿掉的話，他就一定會是 i 減掉第四個硬幣的 value 的 optimal solution →
    $c (i - v_{4})$
💡
$C_{i} = m i n_{j} (1 + C_{i - v_{j}})$

$C_{i}$ 就要追求這四種數值最小的那個
例如：

$C_{28} = m i n_{10} (2 + C_{28 - 20})$

$C_{8} = m i n_{5} (1 + C_{8 - 5})$

$C_{3} = m i n_{1} (3 + C_{3 - 3})$

$C_{28} = m i n_{10} (2) ＋ m i n_{5} (1) + m i n_{1} (3)$

Step 3: Prove Greedy-Choice Property

說明 Greedy-Choice Property 成立

Greedy choice: 選擇最大的幣值但不超過現在的金額
利用矛盾法證明(用 10 ≤ i < 50 例子)
- 我們有個 OPT 可以湊出 i ，greedy choice 要湊出 i 的話一定會拿 10 這個幣值
- 假設沒有任何 OPT 是包含 10 這個幣值的話 → 那麼所有的 OPT 就只能選擇剩下的這幾個 1, 5, 50 來湊成 i
  - 首先先把 50 去掉了，因為他超過 i 了
  - 如果 OPT 裡面存在兩個 5 的話，我一定可以把它換成一個 10 變成一個更好的 OPT，所以這裡最多只會存在一個 5
  - 如果 OPT 裡面存在五個 1，我一定可以把它換成一個 5 變成一個更好的 OPT，所以這裡最多只會存在四個 1
- 那麼在這個限制之下我最多只能湊出 9 塊錢 (5 + 4 = 9)
- 這樣就跟一開始的 10 ≤ i < 50 是矛盾的
這就說明了我們可以直接把小於 i 但數值最大的硬幣放到 OPT 裡面，就可以帶領我們找到最終的 OPT。