蝙蝠岛资源网 Design By www.hbtsch.com
给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。
例如,美国硬币面额有1、5、10、25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。
对于每一种面额,我们都分别计算所需要的硬币数量。具体算法如下:
- 如果全部用1美分的硬币,一共需要36个硬币
- 如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
- 如果用10美分的硬币,则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个硬币
- 如果用25美分的硬币,则需要1个25美分的硬币 + 1个10美分的硬币 + 1个1美分的硬币 = 3个硬币
示意图
方案4的硬币总数最少,因此为最优方案。
具体的代码实现如下:
function minCoinChange(coins, amount) { let result = null; if (!amount) return result; const makeChange = (index, value, min) => { let coin = coins[index]; let newAmount = Math.floor(value / coin); if (newAmount) min[coin] = newAmount; if (value % coin !== 0) { makeChange(--index, value - coin * newAmount, min); } }; const arr = []; for (let i = 0; i < coins.length; i++) { const cache = {}; makeChange(i, amount, cache); arr.push(cache); } console.log(arr); let newMin = 0; arr.forEach(item => { let min = 0; for (let v in item) min += item[v]; if (!newMin || min < newMin) { newMin = min; result = item; } }); return result; }
函数minCoinChange()接收一组硬币的面额,以及要找零的钱数。我们将上面例子中的值传入:
const result = minCoinChange2([1, 5, 10, 25], 36); console.log(result);
得到如下结果:
[ { '1': 36 }, { '1': 1, '5': 7 }, { '1': 1, '5': 1, '10': 3 }, { '1': 1, '10': 1, '25': 1 } ] { '1': 1, '10': 1, '25': 1 }
上面的数组是我们在代码中打印出来的arr的值,用来展示四种不同面额的硬币作为找零硬币时,实际所需要的硬币种类和数量。最终,我们会计算arr数组中硬币总数最少的那个方案,作为minCoinChange()函数的输出。
当然在实际应用中,我们可以把硬币抽象成任何你需要的数字,这个算法能给出你满足结果的最小组合。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
标签:
js,贪心算法,钱币找零
蝙蝠岛资源网 Design By www.hbtsch.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
蝙蝠岛资源网 Design By www.hbtsch.com
暂无js贪心算法 钱币找零问题代码实例的评论...
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
2024年12月26日
2024年12月26日
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]