b028: 忙碌的超商店員

b028: 忙碌的超商店員

還記得有這樣的經驗嗎？你去買一個10元的東西，你付了1張100元的鈔票，店員卻找你9個10元，甚至有找你5個10元4個5元和10個1元的情況。為了避免這樣的情況，某超市在每一間門市都準備了足夠的零錢，並且要求店員找給顧客的零錢個數一定要是最少的。已知這個國家使用的貨幣有1元、5元、10元、12元、16元、20元等6種硬幣，你能幫他解決這個問題嗎？

輸入說明：

輸入一個正整數 N (1<=N<=100)，代表要找的錢。

輸出說明：

請輸出找給顧客 N 元時，最少的零錢個數。

範例輸入：

輸入1:
13

輸入2:
29

範例輸出 ：

輸出1:
2

輸出2:
3

"""
http://uceylove55.blogspot.tw/2015/02/algorithm-greedy-algorithm-part-2.html
演算法 Algorithm ─ Greedy Algorithm PART 2
貪婪演算法 Greedy Algorithm

○ 換零錢遊戲

例：現有 71個 1元，幣值分別為 29元、22元、5元、1元，請用最少的零錢個數兌換零錢。

※  貪婪演算法：
    ○ 局部解 ：     29元    22元    5元    1元
1. 換 29元           2個
2. 換 22元                   0個
3. 換 5元                            2個
4. 換 1元                                   3個
------------------------------------------------------------------------------
      總共換了      2+2+3=  7 枚硬幣

※  動態演算法：    
    ○ 最佳解 ：    29元     22元     5元     1元
1. 換 29元           0個
2. 換 22元                   3個
3. 換 5元                            1個
4. 換 1元                                    0個
--------------------------------------------------------------------------------
      總共換了      3+1=  4 枚硬幣


由此可知：

● 貪婪演算法不一定是最佳解，但效率高
● 動態演算法可以求出最佳解，但效率略差 
● 要依問題的特性判斷採用何種演算法，依此換零錢例子，應該採用動態演算法(Dynamic Programming)
"""

def dynamicCoinChange( T, L ):

Opt = [0 for i in range(0, L+1)]

n = len(T)
for i in range(1, L+1):
smallest = float("inf")
for j in range(0, n):
if (T[j] <= i):
smallest = min(smallest, Opt[i - T[j]]) 
Opt[i] = 1 + smallest 
return Opt[L]


# Coin change situations
problems = [
# [[1, 5, 10, 20, 50, 100, 200],  10000000],
[[1, 3, 4],  20],
[[1, 2, 3],  9],
[[1, 2, 3],  10],
[[1, 5], 13923],
[[7, 22, 71, 231], 753],
[[3, 5, 12], 25],
[[800], 800],
[[2], 50000]
]


# Test Loop
for T, L in problems:
S = dynamicCoinChange(T, L)
print ("dynamicCoinChange(T, L)")
print ("T =", T)
print ("L =", L)
print ("Answer =", S)

T=[1,5,10,12,16,20]
print("1元、5元、10元、12元、16元、20元等6種硬幣")
L=int(input("輸入一個正整數 N (1<=N<=100)，代表要找的錢 > "))
S=dynamicCoinChange( T, L )

print("最少的零錢個數",S)


           

====================== RESTART: F:/Python_APSC/b028.py ======================
dynamicCoinChange(T, L)
T = [1, 3, 4]
L = 20
Answer = 5
dynamicCoinChange(T, L)
T = [1, 2, 3]
L = 9
Answer = 3
dynamicCoinChange(T, L)
T = [1, 2, 3]
L = 10
Answer = 4
dynamicCoinChange(T, L)
T = [1, 5]
L = 13923
Answer = 2787
dynamicCoinChange(T, L)
T = [7, 22, 71, 231]
L = 753
Answer = 7
dynamicCoinChange(T, L)
T = [3, 5, 12]
L = 25
Answer = 4
dynamicCoinChange(T, L)
T = [800]
L = 800
Answer = 1
dynamicCoinChange(T, L)
T = [2]
L = 50000
Answer = 25000
1元、5元、10元、12元、16元、20元等6種硬幣
輸入一個正整數 N (1<=N<=100)，代表要找的錢 > 29
最少的零錢個數 3
>>>