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;
}

函数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使用贪心算法解决找零问题示例
  • js基于贪心算法解决背包问题示例
  • js中的算法与数据结构之列表(list)实例详解
  • nodejs中各种加密算法的实现详解
  • js算法题之查找数字在数组中的索引位置
  • js实现的rc4加密算法示例
  • javascript 中 apply 、call 的详解
  • js使用for循环与innerhtml获取选中tr下td值
  • js阻止事件冒泡的方法详解
  • 使用layui的router来进行传参的实现方法
  • javascript 特性检测并非浏览器检测
  • javascript实现计算个人所得税
  • javascript鼠标滑过显示二级菜单特效
  • 从qq网站中提取的纯js省市区三级联动菜单
  • js上传图片前的限制包括(jpg jpg gif及大小高宽)等
  • ie7提供xmlhttprequest对象为兼容
  • 免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved