---
title: 24-5：貪心法-最少紙幣兌換
lang: zh-tw
tags: DICE Python
---

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

> [name=Chinglin-K]

---

目錄：[Dice 程式教學-Python完整版](https://hackmd.io/@Chinglin-K/Dice-menu)
上一篇：[24-4：窮舉法-百錢百雞問題](https://hackmd.io/@Chinglin-K/Dice-24-4)
下一篇：[24-6：分治法-階乘](https://hackmd.io/@Chinglin-K/Dice-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)

---

## 輸出

---

目錄：[Dice 程式教學-Python完整版](https://hackmd.io/@Chinglin-K/Dice-menu)
上一篇：[24-4：窮舉法-百錢百雞問題](https://hackmd.io/@Chinglin-K/Dice-24-4)
下一篇：[24-6：分治法-階乘](https://hackmd.io/@Chinglin-K/Dice-24-6)

---

:::info

「盡多少本分，得多少本事」😊
:::

---

{%hackmd i1nMRrZcTFmTvoF897K9zg %}