溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了JS使用貪心算法解決找零問題。分享給大家供大家參考，具體如下：
前面介紹了JS貪心算法解決背包問題，這里再來看看找零問題的解決方法。
在現(xiàn)實生活中，經常遇到找零問題，假設有數(shù)目不限的面值為20,10,5,1的硬幣。 給出需要找零數(shù)，求出找零方案，要求：使用數(shù)目最少的硬幣。
對于此類問題，貪心算法采取的方式是找錢時，總是選取可供找錢的硬幣的最大值。比如，需要找錢數(shù)為25時，找錢方式為20+5，而不是10+10+5。
貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明后才能真正運用到題目的算法中。
<script>
var money= [20,10,5,1];
/*
* m[]:存放可供找零的面值，降序排列
* n:需要找零數(shù)
*/
function greedyMoney(m,n){
for(var i=0;i<m.length;i++){
while(n>=m[i] && n>0){
document.write(m[i]+" ");
n = n-m[i];
}
}
document.write("<br>");
}
greedyMoney(money,73);
greedyMoney([25,10,1],63);
</script>
結果是：
20 20 20 10 1 1 1 25 25 10 1 1 1
需要說明的是，在一些情況下，找零錢問題使用貪心算法并不能得到整體最優(yōu)解，其結果可能只是最優(yōu)解的很好近似。
比如，如果提供找零的面值是11，5，1，找零15。
使用貪心算法找零方式為11+1+1+1+1，需要五枚硬幣而最優(yōu)解為5+5+5，只需要3枚硬幣。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript數(shù)學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經查實，將立刻刪除涉嫌侵權內容。
