溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
給定一組硬幣的面額，以及要找零的錢數，計算出符合找零錢數的最少硬幣數量。
例如，美國硬幣面額有1、5、10、25這四種面額，如果要找36美分的零錢，則得出的最少硬幣數應該是1個25美分、1個10美分和1個10美分共三個硬幣。這個算法要解決的就是諸如此類的問題。我們來看看如何用動態規劃的方式來解決。
對于每一種面額，我們都分別計算所需要的硬幣數量。具體算法如下：
示意圖
方案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()函數的輸出。
當然在實際應用中，我們可以把硬幣抽象成任何你需要的數字，這個算法能給出你滿足結果的最小組合。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
