JS使用貪心算法解決找零問(wèn)題示例
本文實(shí)例講述了JS使用貪心算法解決找零問(wèn)題。分享給大家供大家參考，具體如下：
前面介紹了JS貪心算法解決背包問(wèn)題，這里再來(lái)看看找零問(wèn)題的解決方法。
在現(xiàn)實(shí)生活中，經(jīng)常遇到找零問(wèn)題，假設(shè)有數(shù)目不限的面值為20,10,5,1的硬幣。 給出需要找零數(shù)，求出找零方案，要求：使用數(shù)目最少的硬幣。
對(duì)于此類(lèi)問(wèn)題，貪心算法采取的方式是找錢(qián)時(shí)，總是選取可供找錢(qián)的硬幣的最大值。比如，需要找錢(qián)數(shù)為25時(shí)，找錢(qián)方式為20+5，而不是10+10+5。
貪心算法還是很常見(jiàn)的算法之一，這是由于它簡(jiǎn)單易行，構(gòu)造貪心策略不是很困難。
可惜的是，它需要證明后才能真正運(yùn)用到題目的算法中。
<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
需要說(shuō)明的是，在一些情況下，找零錢(qián)問(wèn)題使用貪心算法并不能得到整體最優(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)容感興趣的讀者可查看本站專(zhuān)題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
可以根據(jù)按的鍵盤(pán)上的鍵，顯示鍵盤(pán)動(dòng)作，并顯示keyCode值等2008-06-06
性能優(yōu)化篇之Webpack構(gòu)建代碼質(zhì)量壓縮的建議
這篇文章主要介紹了性能優(yōu)化篇之Webpack構(gòu)建代碼質(zhì)量壓縮的建議，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-04-04
微信小程序選擇器組件picker簡(jiǎn)單入門(mén)
微信小程序picker表單選擇器的使用,根據(jù)官方介紹的有點(diǎn)不清楚,下面這篇文章主要給大家介紹了關(guān)于微信小程序選擇器組件picker的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
輸入密碼時(shí)檢測(cè)大寫(xiě)是否鎖定的js代碼
網(wǎng)站登錄為了更好的用戶(hù)體驗(yàn)都會(huì)在輸入密碼的時(shí)候檢測(cè)是否開(kāi)啟大寫(xiě)。提醒用戶(hù)。2011-02-02
這篇文章主要介紹了JS判斷字符串包含的方法,可有效的檢測(cè)字符串中是否包含固定字符或子字符串,涉及javascript中indexOf的使用技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下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的無(wú)縫滾動(dòng)動(dòng)畫(huà)實(shí)現(xiàn)2
這篇文章主要介紹了基于javascript的無(wú)縫滾動(dòng)動(dòng)畫(huà)實(shí)現(xiàn)2，文章通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
這篇文章主要介紹了Javascript圖片預(yù)加載，幫助大家理解Javascript圖片預(yù)加載的實(shí)現(xiàn)原理，感興趣的小伙伴們可以參考一下2016-02-02
JS 無(wú)法通過(guò)W3C驗(yàn)證的處理方法
今天在頁(yè)面上使用JS時(shí)發(fā)現(xiàn)無(wú)法通過(guò)W3C驗(yàn)證,檢查了一會(huì)發(fā)現(xiàn)此方法可以屏蔽大多數(shù)JS無(wú)法通過(guò)驗(yàn)證的問(wèn)題，簡(jiǎn)單實(shí)用2010-03-03