在現實生活中，常常遇到找零問題，假設有數目不限的面值為20,10,5,1的硬幣。 給出需要找零數，求找零方案，要求：使用數目最少的硬幣。
對於這類問題，貪心演算法採取的方式是找錢時，總是選取可供找錢的硬幣的最大值。例如，需要找錢數為25時，找錢方式為20+5，而不是10+10+5。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，建構貪心策略不是很困難。本文我們就和大家分享JS使用貪心演算法解決找零問題範例。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
<script>
var money= [20,10,5,1];
/*
* m[]:存放可供找零的面值，降序排列
* n:需要找零数
*/
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
要說明的是，在某些情況下，找零錢問題使用貪心演算法並不能得到整體最優解，其結果可能只是最優解的很好近似。
例如，如果提供找零的面值是11，5，1，找零15。
使用貪心演算法找零方式為11+1+1+1+1，需要五枚硬幣而最優解為5+5+5，只需要3枚硬幣。
相關推薦：
以上是JS如何運用貪心演算法解決找零問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！
