DDR爱好者之家 Design By 杰米
给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。
例如,美国硬币面额有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()函数的输出。
当然在实际应用中,我们可以把硬币抽象成任何你需要的数字,这个算法能给出你满足结果的最小组合。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
DDR爱好者之家 Design By 杰米
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
DDR爱好者之家 Design By 杰米
暂无评论...
更新日志
2024年05月15日
2024年05月15日
- 群星.2006-失而复得2辑【新艺宝】【WAV+CUE】
- 《张震岳6CD合集》1993-2000全套[WAV+CUE][3.1G]
- 周华健《粤语精选+国语精选》日本母带 [WAV+CUE][1.2G]
- 《陈楚生6CD合集》[WAV+CUE][2.2G]
- dnf经验胶囊快速获得
- dnf结婚地下城入场材料怎么获得
- dnf结婚戒指属性和婚房属性
- FlorianNoack-IWannaBeLikeYou(2024)【Hi-Res】24bit-96kHz【flac】
- 张国荣.1995-狂恋·国语经典【新艺宝】【WAV+CUE】
- 佛教音乐.2012-《藏传密咒精选集》[FLAC+CUE]
- 微软在Win11中加入内置广告:宣传XGP服务
- 《地狱之刃2》官方:游戏中美景都是取材于真实地点
- 对漫威太失望!叉骨叔确认加盟DC《和平使者》第2季
- 李克勤.1998-寻最这五年2CD【艺能动音】【WAV+CUE】
- 彭莉.1995-感谢你的爱【宝丽金】【WAV+CUE】