Question

某國家發行的貨幣面額有$ \{ a_1,a_2,\dots ,a_k \} $，且$ a_1< a_2 < \dots < a_k $，試問現在有n元，換最少張數的方法為何?

ans

利用greedy algorithm(貪婪演算法)，可能不能換成最少的張數。

Greedy algorithm
簡易說明: 每次拿最佳、最多、優先權最高的解決方式來當最佳解，優點是考慮不須太多，判斷速度快，但衍生出來的問題，可能會會因為順序問題，造成浪費，最後整體不是最佳解的情況發生。

舉例來說:
現在有面額$ 1, 5, 12, 25 $的鈔票，提款機裡有29元，那提款機使用greedy algorithm吐錢，會先給25元1張，然後給1元4張，最後拿到5張紙鈔。
但這不是最佳解，
最佳的方式是12元2張、5元1張，這樣只要拿3張。

那要如何知道最少張數的解呢?
利用動態規劃，可以從表格上找到最少張數的解法。

因為動態需要把問題切到最小來解決，
由上面舉例來說，
要把29元分成0元,1元, 2元,...,28元,29元的情況，
0元沒有可以換，所以為0張，因為1~4元都只能用1換，

直接跳到5元開始討論，
現在可以用1元或5元換，如果用一個1元換，就會剩4元，
這時就可以查表，4元的時候用最少的張數為何，查到是4張1元，
這時表格就可以填5張(5張1元)，
那如果是用一個5元換，那會剩0元，這時查表0元時的最佳解為0張，所以填1(1張5元)，
接著再看5元時，最少張數的是誰，所以最佳解為1張5元，

接著再討論6元的情況，
也是一樣討論假如是拿一張1元或一張5元的情況，
討論拿一張1元，剩5元，查表在5元時最佳解為1(1張5元)，
這時就可填表為2(1張1元+1張5元)，
討論拿一張5元，剩1元，查表在1元時最佳解為1(1張1元)，
這時就可填表為2(1張5元+1張1元)。

以此類推到討論29元的情況。

公式

$n you have.
Discuss all possible sequence: \[ \{i\;|\;0\leq i\leq n\} \] Denomination squence: \[ \{ v_j\;|\;1\leq j\leq k \} \] \[ v_1< v_2<\dots < v_k \] The best solution(the number of counting is the least): \[ M_i = \begin{cases} 0 \text{, if }i=0\\ 1 \text{, if }i=1\\ Min(\{M_{i-v_j}+1\;|\;\text{for }1\leq j\leq k\;\})\text{, if }i\geq v_j\\ \infty \text{, if } i< v_j \end{cases} \] $ i $代表現在討論的錢為多少
$ v_j $為幣值， $ v_1 $為第一個幣值， $ v_2 $為第二個幣值$ \dots $
$ M_i $為現在討論i元時，最少的用量張數。
$ M_{i-v_j} $為現在討論i元時，如果用幣值$ v_j $換的話，$ M_{i-v_j} $就為之前計算過的最少用量張數。
無限大代表不能夠用這幣值換。

題目

換小數目的錢來表格說明，假設銀行有8元，錢面額有1,4,6元，用greedy algorithm，會給一張6元，兩張1元，並不是我們所期望的最少張數。
利用Dynamic Programming來查表，找出最少張數的解法。

表格說明

V: 用什麼幣值來換(拿一張那個幣值的錢後，討論剩下錢幣的最佳解)。
D: 討論現在有多少錢。
這裡多加一些參數去記錄使用哪個幣值的張數，因為只有總張數，回推不容易。
這裡用v代表幣值$ v=\{ 1,4,6 \} $，
$ a_v $代表幣值張數。
$ a_t $代表使用總張數
用黃色代表在這個錢換最少張的最佳解，綠色代表另最佳解。

V\D	0	1	2	3	4	5	6	7	8
1	$ 0 $	$ a_1=1,$ $a_4=0,$ $a_6=0, $ $ a_t=1 $	$a_1=2,$ $a_4=0,$ $a_6=0, $ $a_t=2 $	$a_1=3,$ $a_4=0,$ $a_6=0, $ $a_t=3 $	$a_1=4,$ $a_4=0,$ $a_6=0, $ $a_t=4 $	$a_1=1,$ $a_4=1,$ $a_6=0, $ $a_t=2 $	$a_1=2,$ $a_4=1,$ $a_6=0, $ $a_t=3 $	$a_1=1,$ $a_4=0,$ $a_6=1, $ $a_t=2 $	$a_1=2,$ $a_4=0,$ $a_6=1, $ $a_t=3 $
4	0	-	-	-	$a_1=0,$ $a_4=1,$ $a_6=0, $ $a_t=1 $	$a_1=1,$ $a_4=1,$ $a_6=0, $ $a_t=2 $	$a_1=2,$ $a_4=1,$ $a_6=0, $ $a_t=3 $	$a_1=3,$ $a_4=1,$ $a_6=0, $ $a_t=4 $	$a_1=0,$ $a_4=2,$ $a_6=0, $ $a_t=2 $
6	0	-	-	-	-	-	$a_1=0,$ $a_4=0,$ $a_6=1, $ $a_t=1 $	$a_1=1,$ $a_4=0,$ $a_6=1, $ $a_t=2 $	$a_1=2,$ $a_4=0,$ $a_6=1, $ $a_t=3 $

說明

在programming的時候，可以多加一些參數去紀錄討論過程和結果，以便後續回推使用。

從2元開始討論，
如果拿一張1元，會剩下1元，查表在1元時最佳解為1張，所以+1，為2張。
4元不能換，6元不能換。所以最佳解為2張。

討論3元，跟2元時一樣，以此類推到後面，

現在在討論8元，
如果拿一張1元，會剩下7元，查表在7元時最佳解為2張，所以會需要3張才能湊滿8元。
如果拿一張4元，會剩下4元，查表在4元時最佳解為1張，所以會需要2張才能湊滿8元。
如果拿一張6元，會剩下2元，查表在2元時最佳解為2張，所以會需要3張才能湊滿8元。
最後得出在8元時，最少張數為2張。

V\D	0	1	2	3	4	5	6	7	8
1	\( 0 \)	\( a_1=1,\) \(a_4=0,\) \(a_6=0, \) \( a_t=1 \)	\(a_1=2,\) \(a_4=0,\) \(a_6=0, \) \(a_t=2 \)	\(a_1=3,\) \(a_4=0,\) \(a_6=0, \) \(a_t=3 \)	\(a_1=4,\) \(a_4=0,\) \(a_6=0, \) \(a_t=4 \)	\(a_1=1,\) \(a_4=1,\) \(a_6=0, \) \(a_t=2 \)	\(a_1=2,\) \(a_4=1,\) \(a_6=0, \) \(a_t=3 \)	\(a_1=1,\) \(a_4=0,\) \(a_6=1, \) \(a_t=2 \)	\(a_1=2,\) \(a_4=0,\) \(a_6=1, \) \(a_t=3 \)
4	0	-	-	-	\(a_1=0,\) \(a_4=1,\) \(a_6=0, \) \(a_t=1 \)	\(a_1=1,\) \(a_4=1,\) \(a_6=0, \) \(a_t=2 \)	\(a_1=2,\) \(a_4=1,\) \(a_6=0, \) \(a_t=3 \)	\(a_1=3,\) \(a_4=1,\) \(a_6=0, \) \(a_t=4 \)	\(a_1=0,\) \(a_4=2,\) \(a_6=0, \) \(a_t=2 \)
6	0	-	-	-	-	-	\(a_1=0,\) \(a_4=0,\) \(a_6=1, \) \(a_t=1 \)	\(a_1=1,\) \(a_4=0,\) \(a_6=1, \) \(a_t=2 \)	\(a_1=2,\) \(a_4=0,\) \(a_6=1, \) \(a_t=3 \)