js貪心算法 錢幣找零問題代碼實例
給定一組硬幣的面額，以及要找零的錢數(shù)，計算出符合找零錢數(shù)的最少硬幣數(shù)量。
例如，美國硬幣面額有1、5、10、25這四種面額，如果要找36美分的零錢，則得出的最少硬幣數(shù)應(yīng)該是1個25美分、1個10美分和1個10美分共三個硬幣。這個算法要解決的就是諸如此類的問題。我們來看看如何用動態(tài)規(guī)劃的方式來解決。
對于每一種面額，我們都分別計算所需要的硬幣數(shù)量。具體算法如下：
- 如果全部用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的硬幣總數(shù)最少，因此為最優(yōu)方案。
具體的代碼實現(xiàn)如下：
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;
}
函數(shù)minCoinChange()接收一組硬幣的面額，以及要找零的錢數(shù)。我們將上面例子中的值傳入：
const result = minCoinChange2([1, 5, 10, 25], 36); console.log(result);
得到如下結(jié)果：
[
{ '1': 36 },
{ '1': 1, '5': 7 },
{ '1': 1, '5': 1, '10': 3 },
{ '1': 1, '10': 1, '25': 1 }
]
{ '1': 1, '10': 1, '25': 1 }
上面的數(shù)組是我們在代碼中打印出來的arr的值，用來展示四種不同面額的硬幣作為找零硬幣時，實際所需要的硬幣種類和數(shù)量。最終，我們會計算arr數(shù)組中硬幣總數(shù)最少的那個方案，作為minCoinChange()函數(shù)的輸出。
當(dāng)然在實際應(yīng)用中，我們可以把硬幣抽象成任何你需要的數(shù)字，這個算法能給出你滿足結(jié)果的最小組合。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了原生js自定義右鍵菜單，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
小程序云開發(fā)教程如何使用云函數(shù)實現(xiàn)點贊功能
這篇文章主要為大家詳細(xì)介紹了小程序云開發(fā)教程如何使用云函數(shù)實現(xiàn)點贊功能，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05
Bun運行時是新一代高性能JavaScript/TypeScript運行時
Bun由Jarred Sumner創(chuàng)建,是一款新興的JavaScript和TypeScript運行時,旨在比Node.js和Deno提供更高性能和快速啟動,Bun使用Zig語言編寫,內(nèi)置包管理并支持Node.js大部分API,適用于高并發(fā)API服務(wù)和快速構(gòu)建工具2024-11-11
JavaScript使用localStorage存儲數(shù)據(jù)
這篇文章主要為大家詳細(xì)介紹了JavaScript使用localStorage存儲數(shù)據(jù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09
event.keyCode鍵碼值表 附只能輸入特定的字符串代碼
非常不錯的應(yīng)用，讓文本框里只能輸入money大家看下具體的實現(xiàn)代碼，真是只有想到，原理很簡單。2009-05-05
調(diào)試JavaScript是一件很麻煩的事，盡管有很多很好用的調(diào)試工具，但有時候想要跟蹤值的變化，但即不想中斷腳本執(zhí)行，也不想用alert顯示值信息，這種情況下，一般的做法是在頁面上添加一個DIV或者其它元素，然后再往里面添加調(diào)試信息。2010-02-02
關(guān)于使用runtimeStyle屬性問題討論文章
關(guān)于使用runtimeStyle屬性問題討論文章...2007-03-03
深入解析JS實現(xiàn)3D標(biāo)簽云的原理與方法
這篇文章主要介紹了深入解析JS實現(xiàn)3D標(biāo)簽云的原理與方法,結(jié)合實例形式詳細(xì)分析了3D標(biāo)簽云原理、實現(xiàn)技巧與相關(guān)操作注意事項,需要的朋友可以參考下2019-08-08
JavaScript模擬實現(xiàn)Promise功能的示例代碼
這篇文章主要為大家詳細(xì)介紹了JavaScript如何模擬實現(xiàn)Promise功能，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)JavaScript有一定的幫助，需要的可以參考一下2022-12-12
這篇文章主要為大家詳細(xì)介紹了axios實現(xiàn)簡單文件上傳功能，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09