JS使用貪心算法解決找零問題示例

更新時間：2017年11月27日 14:42:14 作者：yu_meiguang

這篇文章主要介紹了JS使用貪心算法解決找零問題,簡單描述了找零問題,并結合具體實例分析了javascript使用貪心算法解決找零問題的相關實現(xiàn)技巧,需要的朋友可以參考下

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

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

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

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

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

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

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

結果是：

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

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

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

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

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

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

您可能感興趣的文章:

原生js實現(xiàn)簡單輪播圖
這篇文章主要為大家詳細介紹了原生js實現(xiàn)簡單輪播圖，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-10-10
Bootstrap教程JS插件彈出框學習筆記分享
這篇文章主要為大家分享了Bootstrap教程JS插件彈出框學習筆記，為大家詳細介紹Bootstrap彈出框的使用方法，感興趣的小伙伴們可以參考一下
2016-05-05
原生JavaScript實現(xiàn)輪播圖效果
這篇文章主要為大家詳細介紹了原生JavaScript實現(xiàn)輪播圖效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-09-09
javascript面向對象三大特征之多態(tài)實例詳解
這篇文章主要介紹了javascript面向對象三大特征之多態(tài),結合實例形式詳細分析了javascript面向對象程序設計中多態(tài)的概念、原理,并結合實例形式總結了多態(tài)的實現(xiàn)方法與使用技巧,需要的朋友可以參考下
2019-07-07
JavaScript 接收鍵盤指令示例
JavaScript接收鍵盤指令示例，按下鍵盤上不同的鍵，程序會跳轉到不同的網(wǎng)頁，本例中按下A鍵程序為跳轉到腳本之家的首頁，實現(xiàn)按鍵跳轉的功能。
2009-10-10
第七章之菜單按鈕圖標組件
Bootstrap，來自 Twitter，是目前最受歡迎的前端框架。這篇文章主要介紹BootStrap組件之菜單按鈕圖標組件的相關資料,需要的朋友可以參考下
2016-04-04
javascript關于繼承的用法匯總
這篇文章主要介紹了javascript關于繼承的用法,實例匯總了常見的javascript關于繼承的用法,具有一定的參考借鑒價值,需要的朋友可以參考下
2014-12-12
詳解JavaScript?(!!)?中的雙感嘆號是干什么用的
JavaScript?不是靜態(tài)語言，而是動態(tài)語言，這意味著變量可以引用或保存任何類型的值，此外，該類型可以隨時更改，這篇文章主要介紹了JavaScript?(!!)?中的雙感嘆號作用,需要的朋友可以參考下
2022-09-09
ES10的13個新特性示例(小結)
這篇文章主要介紹了ES10的13個新特性示例(小結)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-09-09
JS Promise axios 請求結果后面的.then() 是什么意思
本文主要介紹了JS Promise axios 請求結果后面的 .then() 是什么意思，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-01-01