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
>>>
沒有留言:
張貼留言