24-5：貪心法-最少紙幣兌換

Chinglin-K

目錄：Dice 程式教學-Python完整版
上一篇：24-4：窮舉法-百錢百雞問題
下一篇：24-6：分治法-階乘

題目

貪婪演算法：
在進行解決問題的過程中，把問題分成數個子問題，每個子問題都選擇當前最佳最有利的選擇/解答，
直到解決問題為止。
Step1：定義貪婪準則
根據此貪婪準則，不斷找出目前小問題的最佳解。
Step2：不斷重複貪婪準則，直到解決問題為止
不斷的使用貪婪準則,，找出每個小問題的最佳解，直到解決問題為止。

以最少紙幣兌換為例：
問題: 要把 n 元(n<=1000)，兌換成1000元、 500 元, 100 元, 5 元, 1 元紙幣,
如何兌換可以讓最終的紙幣數最少?
程式可以重複輸入，直到輸入的金額為0。

輸入範例:
967
73
39
525
0
輸出範例:
1張500元 4張100元 1張50元 1張10元 1張5元 2張1元
0張500元 0張100元 1張50元 2張10元 0張5元 3張1元
0張500元 0張100元 0張50元 3張10元 1張5元 4張1元
1張500元 0張100元 0張50元 2張10元 1張5元 0張1元

程式碼
















money=[500,100,50,10,5,1]

def count(n,m):
    if(m<6 or n>0):
        x=n//money[m]
        print(f'{x}張{money[m]}元',end=" ")
        return count(n%money[m],m+1)
    else:
        print()
        return 1

while True:
    a=int(input())
    if(a==0):
        break
    count(a,0)