首頁 > web前端 > js教程 > JS如何運用貪心演算法解決找零問題

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

小云云
發布: 2017-12-07 15:57:40
原創
2828 人瀏覽過

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

對於這類問題,貪心演算法採取的方式是找錢時,總是選取可供找錢的硬幣的最大值。例如,需要找錢數為25時,找錢方式為20+5,而不是10+10+5。

貪心演算法還是很常見的演算法之一,這是由於它簡單易行,建構貪心策略不是很困難。本文我們就和大家分享JS使用貪心演算法解決找零問題範例。

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


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

登入後複製


結果是:


1

2

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中文網其他相關文章!

相關標籤:
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
怎麼實作 JavaScript點與圓的位置關係
來自於 1970-01-01 08:00:00
0
0
0
JavaScript鉤子函數是什麼?
來自於 1970-01-01 08:00:00
0
0
0
c++ 呼叫javascript
來自於 1970-01-01 08:00:00
0
0
0
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板