硬幣兌換問(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 # 輸入可換的硬幣種類(lèi)，總金額n
changeCoins(coins, n)
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
