JS如何運用貪心演算法解決找零問題

在現實生活中，常常遇到找零問題，假設有數目不限的面值為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實作找零張數最小

Python實現的一個找零錢的小程式碼分享

找零錢的兩個方法

以上是JS如何運用貪心演算法解決找零問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！