Python 硬幣兌換問題
更新時(shí)間：2019年07月29日 10:14:08 作者：GorillaNotes
這篇文章主要介紹了Python 硬幣兌換問題，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
硬幣兌換問題：
給定總金額為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)過本次兌換后所剩下的面值，即 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)
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Python實(shí)現(xiàn)類似jQuery使用中的鏈?zhǔn)秸{(diào)用的示例
chained calls鏈?zhǔn)秸{(diào)用其實(shí)多是指一種方法鏈的程序?qū)懛?這里我們來看一下Python實(shí)現(xiàn)類似jQuery使用中的鏈?zhǔn)秸{(diào)用的示例,首先說明一下什么是鏈?zhǔn)秸{(diào)用:2016-06-06
這篇文章主要介紹了Python編程中字符串和列表的基本知識(shí)講解,是Python入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-10-10
這篇文章主要介紹了python字符串替換示例,需要的朋友可以參考下2014-04-04
python使用mitmproxy抓取瀏覽器請(qǐng)求的方法
今天小編就為大家分享一篇python使用mitmproxy抓取瀏覽器請(qǐng)求的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-07-07
python操作注冊(cè)表的方法實(shí)現(xiàn)
Python提供了winreg模塊,可以用于操作Windows注冊(cè)表,本文就來介紹一下python操作注冊(cè)表的方法實(shí)現(xiàn),主要包括打開注冊(cè)表、讀取注冊(cè)表值、寫入注冊(cè)表值和關(guān)閉注冊(cè)表,具有一定的參考價(jià)值,感興趣的可以了解一下2023-08-08
python實(shí)現(xiàn)大文本文件分割成多個(gè)小文件
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)大文本文件分割成多個(gè)小文件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04
Python使用datetime庫實(shí)現(xiàn)對(duì)時(shí)間的獲取方法
這篇文章通過一個(gè)簡單示例給大家介紹了Python如何使用datetime庫實(shí)現(xiàn)對(duì)時(shí)間的獲取方法,文章通過代碼示例給大家介紹的非常詳細(xì),具有一定的參考價(jià)值,需要的朋友可以參考下2023-11-11
Python itertools.product方法代碼實(shí)例
這篇文章主要介紹了Python itertools.product方法代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
這篇文章主要為大家詳細(xì)介紹了利用aardio給python編寫圖形界面的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08
這篇文章主要介紹了python批量圖片處理,涉及Python針對(duì)圖片文件的遍歷、判斷、縮放等相關(guān)操作技巧,需要的朋友可以參考下2019-08-08