DDR爱好者之家

js贪心算法 钱币找零问题代码实例
站长资源 2024/11/25 佚名
53 1538
DDR爱好者之家 Design By 杰米

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

例如，美国硬币面额有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个硬币

示意图

js贪心算法 钱币找零问题代码实例

方案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 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米