硬币兑换问题:
给定总金额为A的一张纸币,现要兑换成面额分别为a1,a2,....,an的硬币,且希望所得到的硬币个数最少。
# 动态规划思想 dp方程式如下 # dp[0] = 0 # dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length # 回溯法,输出可找的硬币方案 # path[i] 表示经过本次兑换后所剩下的面值,即 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 # 初始化当前硬币最优值 for c in coins: # 扫描一遍硬币列表,选择一个最优值 if i >= c and minNum > dp[i-c]+1: minNum, path[i] = dp[i-c]+1, i - c dp[i] = minNum # 更新当前硬币最优值 print('最少硬币数:', 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)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
标签:
Python,硬币兑换
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
白云城资源网 Copyright www.dyhadc.com
暂无“Python 硬币兑换问题”评论...
更新日志
2024年10月07日
2024年10月07日
- 群星《前途海量 电影原声专辑》[FLAC/分轨][227.78MB]
- 张信哲.1992-知道新曲与精丫巨石】【WAV+CUE】
- 王翠玲.1995-ANGEL【新艺宝】【WAV+CUE】
- 景冈山.1996-我的眼里只有你【大地唱片】【WAV+CUE】
- 群星《八戒 电影原声带》[320K/MP3][188.97MB]
- 群星《我的阿勒泰 影视原声带》[320K/MP3][139.47MB]
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[320K/MP3][148.91MB]
- 刘雅丽.2001-丽花皇后·EMI精选王【EMI百代】【FLAC分轨】
- 齐秦.1994-黄金十年1981-1990CHINA.TOUR.LIVE精丫上华】【WAV+CUE】
- 群星.2008-本色·百代音乐人创作专辑【EMI百代】【WAV+CUE】
- 群星.2001-同步过冬AVCD【环球】【WAV+CUE】
- 群星.2020-同步过冬2020冀待晴空【环球】【WAV+CUE】
- 沈雁.1986-四季(2012梦田复刻版)【白云唱片】【WAV+CUE】
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[FLAC/分轨][257.88MB]
- 《国语老歌 怀旧篇 3CD》[WAV/分轨][1.6GB]