找零兑换-动态规划算法

动态规划算法

def?dpMakeChange(coin_value_li,change,min_coins,coins_used):
????"""
????:param?coin_value_li:?币值的列表
????:param?change:?需要找零的价格
????:param?min_coins:?列表
????:param?conis_used:?列表
????:return:
????"""
????for?cents?in?range(change+1):
????????coin_count=cents
????????new_coin=1
????????for?j?in?[c?for?c?in?coin_value_li?if?c<=cents]:
????????????if?min_coins[cents-j]?+1?<coin_count:
????????????????coin_count=min_coins[cents-j]?+1
????????????????new_coin?=?j
????????min_coins[cents]?=?coin_count
????????coins_used[cents]=new_coin
????return?min_coins[change]

def?printCoins(coins_used,change):
????coin=change
????while?coin?>0:
????????this_coin=coins_used[coin]
????????print(this_coin)
????????coin=coin-this_coin


amnt=63
coin_li=[1,5,10,21,25]
coin_used=[0]*(amnt+1)
coin_count=[0]*(amnt+1)

print(f'需要找零兑换：{amnt}')
print(dpMakeChange(coin_li,amnt,coin_count,coin_used),'coins')
printCoins(coin_used,amnt)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!