JavaScript贪心算法实现钱币找零问题
作者：木棉时间：2026-10-23 11:00:54浏览：164
本文介绍如何使用JavaScript中的贪心算法解决钱币找零问题，通过计算不同面额硬币的组合，找出满足找零金额所需的最少硬币数量。以美国硬币面额为例，演示了从1美分到25美分的计算过程，并提供了完整的代码实现与结果分析。
贪心算法解决钱币找零问题
已知硬币面额集合与目标找零金额，求解满足该金额所需的最少硬币枚数。
以美国硬币为例，面额包括1、5、10、25美分。若需找零36美分，最优解为1枚25美分、1枚10美分和1枚1美分，共计3枚。本文旨在探讨此类问题的动态规划解法。
针对每种面额分别计算所需硬币数量，具体算法逻辑如下：
- 若全使用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的硬币总数最少，因此为最优方案。
JavaScript代码实现
具体的代码实现如下：
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中将数组和对象混合组装为JSON字符串
2026-11-05 16:41:42
JS运算符优先级与结合性的区别是什么？
2026-11-05 13:22:02
JS Map怎么只遍历Key或Value
2026-11-05 13:00:36
D3.js 与 ECharts 选型对比：灵活性 vs 开发效率
2026-11-05 09:45:01
为什么JS中typeof []返回object：数组类型检测误区解析
2026-11-04 19:50:47