ADA 7.3: Coin Changing 找零錢問題

###### 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 元 :::info 💡 用這個方法就可以拿到 OPT 嗎？要怎麼證明呢？ ::: # Step 1: Cast Optimization Problem :::info 💡 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)$ :::info 💡 $C_i = min_j(1+C_{i-v_j})$ $C_i$ 就要追求這四種數值最小的那個例如： $C_{28} = min_{10}(2+C_{28-20})$ $C_8 = min_5(1+C_{8-5})$ $C_3=min_1(3+C_{3-3})$ $C_{28} = min_{10}(2)＋min_5(1)+min_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。