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

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

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

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

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

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

<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>

結(jié)果是：

20 20 20 10 1 1 125 25 10 1 1 1

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

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

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

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

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