小程序开发怎么布局_js贪心算法 钱币找零问题代

2021-01-07 11:20 admin
js贪心算法 钱币找零问题代码实例     ''s home   这篇文章主要介绍了js贪心算法 钱币找零问题代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

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

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

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

如果全部用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的硬币总数最少,因此为最优方案。

具体的代码实现如下:

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()函数的输出。

当然在实际应用中,我们可以把硬币抽象成任何你需要的数字,这个算法能给出你满足结果的最小组合。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持凡科。