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