給定一組硬幣的面額，以及要找零的錢數，計算出符合找零錢數的最少硬幣數量。
例如，美國硬幣面額有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()函數的輸出。
當然在實際應用中，我們可以把硬幣抽象成任何你需要的數字，這個算法能給出你滿足結果的最小組合。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
