快上网专注成都网站设计 成都网站制作 成都网站建设
成都网站建设公司服务热线:028-86922220

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

js贪心算法钱币找零问题代码实例-创新互联

给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。

宜城网站建设公司创新互联建站,宜城网站设计制作,有大型网站制作公司丰富经验。已为宜城成百上千家提供企业网站建设服务。企业网站搭建\成都外贸网站制作要多少钱,请找那个售后服务好的宜城做网站的公司定做!

例如,美国硬币面额有1、5、10、25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。

对于每一种面额,我们都分别计算所需要的硬币数量。具体算法如下:

  1. 如果全部用1美分的硬币,一共需要36个硬币
  2. 如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
  3. 如果用10美分的硬币,则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个硬币
  4. 如果用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;
}

网站名称:js贪心算法钱币找零问题代码实例-创新互联
网页链接:http://6mz.cn/article/dssgdo.html

其他资讯