本文實例講述了JS使用貪心算法解決找零問題。分享給大家供大家參考，具體如下：

前面介紹了JS貪心算法解決背包問題，這里再來看看找零問題的解決方法。

在現實生活中，經常遇到找零問題，假設有數目不限的面值為20,10,5,1的硬幣。 給出需要找零數，求出找零方案，要求：使用數目最少的硬幣。

對于此類問題，貪心算法采取的方式是找錢時，總是選取可供找錢的硬幣的最大值。比如，需要找錢數為25時，找錢方式為20+5，而不是10+10+5。

貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。

可惜的是，它需要證明后才能真正運用到題目的算法中。

<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 125 25 10 1 1 1

需要說明的是，在一些情況下，找零錢問題使用貪心算法并不能得到整體最優解，其結果可能只是最優解的很好近似。

比如，如果提供找零的面值是11，5，1，找零15。

使用貪心算法找零方式為11+1+1+1+1，需要五枚硬幣而最優解為5+5+5，只需要3枚硬幣。

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

希望本文所述對大家JavaScript程序設計有所幫助。