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ì)于此類問(wèn)題，貪心算法采取的方式是找錢時(shí)，總是選取可供找錢的硬幣的最大值。比如，需要找錢數(shù)為25時(shí)，找錢方式為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ō)明的是，在一些情況下，找零錢問(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)容感興趣的讀者可查看本站專題：《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)文章
這篇文章主要為大家詳細(xì)介紹了原生js實(shí)現(xiàn)簡(jiǎn)單輪播圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-10-10
Bootstrap教程JS插件彈出框?qū)W習(xí)筆記分享
這篇文章主要為大家分享了Bootstrap教程JS插件彈出框?qū)W習(xí)筆記，為大家詳細(xì)介紹Bootstrap彈出框的使用方法，感興趣的小伙伴們可以參考一下2016-05-05
原生JavaScript實(shí)現(xiàn)輪播圖效果
這篇文章主要為大家詳細(xì)介紹了原生JavaScript實(shí)現(xiàn)輪播圖效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
javascript面向?qū)ο笕筇卣髦鄳B(tài)實(shí)例詳解
這篇文章主要介紹了javascript面向?qū)ο笕筇卣髦鄳B(tài),結(jié)合實(shí)例形式詳細(xì)分析了javascript面向?qū)ο蟪绦蛟O(shè)計(jì)中多態(tài)的概念、原理,并結(jié)合實(shí)例形式總結(jié)了多態(tài)的實(shí)現(xiàn)方法與使用技巧,需要的朋友可以參考下2019-07-07
JavaScript接收鍵盤指令示例，按下鍵盤上不同的鍵，程序會(huì)跳轉(zhuǎn)到不同的網(wǎng)頁(yè)，本例中按下A鍵程序?yàn)樘D(zhuǎn)到腳本之家的首頁(yè)，實(shí)現(xiàn)按鍵跳轉(zhuǎn)的功能。2009-10-10
Bootstrap，來(lái)自 Twitter，是目前最受歡迎的前端框架。這篇文章主要介紹BootStrap組件之菜單按鈕圖標(biāo)組件的相關(guān)資料,需要的朋友可以參考下2016-04-04
這篇文章主要介紹了javascript關(guān)于繼承的用法,實(shí)例匯總了常見(jiàn)的javascript關(guān)于繼承的用法,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-12-12
詳解JavaScript?(!!)?中的雙感嘆號(hào)是干什么用的
JavaScript?不是靜態(tài)語(yǔ)言，而是動(dòng)態(tài)語(yǔ)言，這意味著變量可以引用或保存任何類型的值，此外，該類型可以隨時(shí)更改，這篇文章主要介紹了JavaScript?(!!)?中的雙感嘆號(hào)作用,需要的朋友可以參考下2022-09-09
這篇文章主要介紹了ES10的13個(gè)新特性示例(小結(jié))，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
JS Promise axios 請(qǐng)求結(jié)果后面的.then() 是什么意思
本文主要介紹了JS Promise axios 請(qǐng)求結(jié)果后面的 .then() 是什么意思，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01