十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。
宜城网站建设公司创新互联建站,宜城网站设计制作,有大型网站制作公司丰富经验。已为宜城成百上千家提供企业网站建设服务。企业网站搭建\成都外贸网站制作要多少钱,请找那个售后服务好的宜城做网站的公司定做!例如,美国硬币面额有1、5、10、25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。
对于每一种面额,我们都分别计算所需要的硬币数量。具体算法如下:
示意图
方案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; }