Python 硬幣兌換問題
更新時間：2019年07月29日 10:14:08 作者：GorillaNotes
這篇文章主要介紹了Python 硬幣兌換問題，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
硬幣兌換問題：
給定總金額為A的一張紙幣，現(xiàn)要兌換成面額分別為a1,a2,....,an的硬幣，且希望所得到的硬幣個數(shù)最少。
# 動態(tài)規(guī)劃思想 dp方程式如下
# dp[0] = 0
# dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length
# 回溯法，輸出可找的硬幣方案
# path[i] 表示經(jīng)過本次兌換后所剩下的面值，即 i - path[i] 可得到本次兌換的硬幣值。
def changeCoins(coins, n):
if n < 0: return None
dp, path = [0] * (n+1), [0] * (n+1) # 初始化
for i in range(1, n+1):
minNum = i # 初始化當前硬幣最優(yōu)值
for c in coins: # 掃描一遍硬幣列表，選擇一個最優(yōu)值
if i >= c and minNum > dp[i-c]+1:
minNum, path[i] = dp[i-c]+1, i - c
dp[i] = minNum # 更新當前硬幣最優(yōu)值
print('最少硬幣數(shù):', dp[-1])
print('可找的硬幣', end=': ')
while path[n] != 0:
print(n-path[n], end=' ')
n = path[n]
print(n, end=' ')
if __name__ == '__main__':
coins, n = [1, 4, 5], 22 # 輸入可換的硬幣種類，總金額n
changeCoins(coins, n)
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
python unittest實現(xiàn)api自動化測試
這篇文章主要為大家詳細介紹了python unittest實現(xiàn)api自動化測試的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
python創(chuàng)建與遍歷List二維列表的方法
這篇文章主要介紹了python創(chuàng)建與遍歷List二維列表的方法，本文給大家介紹的非常詳細，具有一定的參考借鑒價值 ,需要的朋友可以參考下2019-08-08
這篇文章主要為大家詳細介紹了TensorFlow實現(xiàn)Logistic回歸的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-09-09
這篇文章主要介紹了python如何通過閉包實現(xiàn)計算器的功能,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友可以參考下2020-02-02
這篇文章主要為大家介紹了Python線程編程之Thread，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
在本篇內(nèi)容里小編給大家整理了一篇關(guān)于python不同版本的_new_不同點總結(jié)內(nèi)容，有興趣的朋友們可以學(xué)習下。2020-12-12
這篇文章主要介紹了Python實現(xiàn)的knn算法,結(jié)合實例形式詳細分析了Python實現(xiàn)knn算法的原理與相關(guān)操作技巧,并附帶給出了statsmodels模塊與pandas模塊的下載、安裝操作方法,需要的朋友可以參考下2018-06-06
這篇文章主要為大家詳細介紹了Python實現(xiàn)信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要介紹了python 字典修改鍵(key)的幾種方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-08-08
Matplotlib是一個Python的2D繪圖庫,通過Matplotlib開發(fā)者可以僅需要幾行代碼,便可以生成繪圖,直方圖,功率譜,條形圖,錯誤圖,散點圖等,這篇文章主要給大家介紹了Python中如何使用Matplotlib庫繪制圖形的相關(guān)資料2022-07-07