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