JS使用貪心算法解決找零問題示例
更新時間：2017年11月27日 14:42:14 作者：yu_meiguang
這篇文章主要介紹了JS使用貪心算法解決找零問題,簡單描述了找零問題,并結合具體實例分析了javascript使用貪心算法解決找零問題的相關實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了JS使用貪心算法解決找零問題。分享給大家供大家參考，具體如下：
前面介紹了JS貪心算法解決背包問題，這里再來看看找零問題的解決方法。
在現(xiàn)實生活中，經常遇到找零問題，假設有數(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程序設計有所幫助。
相關文章
可以根據(jù)按的鍵盤上的鍵，顯示鍵盤動作，并顯示keyCode值等2008-06-06
這篇文章主要介紹了性能優(yōu)化篇之Webpack構建代碼質量壓縮的建議，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-04-04
微信小程序picker表單選擇器的使用,根據(jù)官方介紹的有點不清楚,下面這篇文章主要給大家介紹了關于微信小程序選擇器組件picker的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-03-03
網站登錄為了更好的用戶體驗都會在輸入密碼的時候檢測是否開啟大寫。提醒用戶。2011-02-02
這篇文章主要介紹了JS判斷字符串包含的方法,可有效的檢測字符串中是否包含固定字符或子字符串,涉及javascript中indexOf的使用技巧,非常簡單實用,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了JS深拷貝與淺拷貝的相關資料，文中講解非常細致，代碼幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-08-08
設置iframe的document.designMode后僅Firefox中其body.innerHTML為br
設置iframe的document.designMode為On可以讓其可編輯，一般用在富文本編輯器組件中。這里僅列出各瀏覽器差異2012-02-02
這篇文章主要介紹了基于javascript的無縫滾動動畫實現(xiàn)2，文章通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
這篇文章主要介紹了Javascript圖片預加載，幫助大家理解Javascript圖片預加載的實現(xiàn)原理，感興趣的小伙伴們可以參考一下2016-02-02
今天在頁面上使用JS時發(fā)現(xiàn)無法通過W3C驗證,檢查了一會發(fā)現(xiàn)此方法可以屏蔽大多數(shù)JS無法通過驗證的問題，簡單實用2010-03-03