JS基于貪心算法解決背包問題示例
更新時間：2017年11月27日 14:23:24 作者：Spider--Man
這篇文章主要介紹了JS基于貪心算法解決背包問題,簡單說明了貪心算法的概念、原理,并結(jié)合具體實例形式分析了JS使用貪心算法解決部分背包問題的具體操作技巧,需要的朋友可以參考下
本文實例講述了JS基于貪心算法解決背包問題。分享給大家供大家參考，具體如下：
貪心算法：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
尋找最優(yōu)解的過程，目的是得到當前最優(yōu)解
部分背包問題：固定容積的背包能放入物品的總最大價值
物品 A B C D
價格 50 220 60 60
尺寸 5 20 10 12
比率 10 11 6 5
按比例降序盡可能多放入物品
function greedy(values, weights, capacity){
var returnValue = 0
var remainCapacity = capacity
var sortArray = []
values.map((cur, index) =>{
sortArray.push({
'value': values[index],
'weight': weights[index],
'ratio': values[index]/weights[index]
})
})
sortArray.sort(function(a, b){
return b.ratio > a.ratio
})
console.log(sortArray)
sortArray.map((cur,index) => {
var num = parseInt(remainCapacity/cur.weight)
console.log(num)
remainCapacity -= num*cur.weight
returnValue += num*cur.value
})
return returnValue
}
var items = ['A','B','C','D']
var values = [50,220,60,60]
var weights = [5,20,10,12]
var capacity = 32 //背包容積
greedy(values, weights, capacity) // 320
更多關(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)文章
本文主要介紹了原生js實現(xiàn)彈出層效果的示例代碼。具有一定的參考價值，下面跟著小編一起來看下吧2017-01-01
JavaScript中全局變量、函數(shù)內(nèi)變量以及常量表達式的效率測試
直接用字符串常量要比利用全局變量快，但創(chuàng)建正則表達式就比起用全局變量要慢上很多了。2009-11-11
微信小程序骨架屏的應(yīng)用與實現(xiàn)步驟詳細記錄
所謂骨架屏就是在頁面數(shù)據(jù)尚未加載前先給用戶展示出頁面的大致結(jié)構(gòu),直到請求數(shù)據(jù)返回后再渲染頁面,補充進需要顯示的數(shù)據(jù)內(nèi)容,這篇文章主要給大家介紹了關(guān)于微信小程序骨架屏的應(yīng)用與實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-05-05
這篇文章是一段關(guān)于js點擊文本框后才加載驗證碼實例代碼，而不是直接顯示驗證碼，感興趣的小伙伴們可以參考一下2015-10-10
js實現(xiàn)仿愛微網(wǎng)兩級導(dǎo)航菜單效果代碼
這篇文章主要介紹了js實現(xiàn)仿愛微網(wǎng)兩級導(dǎo)航菜單效果代碼,通過javascript自定義函數(shù)結(jié)合鼠標點擊事件實現(xiàn)tab切換的功能,具有一定參考借鑒價值,需要的朋友可以參考下2015-08-08
我們在做小程序支付相關(guān)的開發(fā)時,總會遇到這些難題,下面這篇文章主要給大家介紹了關(guān)于微信小程序調(diào)用支付接口的完整流程,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-02-02
這篇文章主要介紹了微信小程序 下拉列表的實現(xiàn)實例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03
js利用正則表達式檢驗輸入內(nèi)容是否為網(wǎng)址
這篇文章主要為大家詳細介紹了js利用正則表達式檢驗輸入內(nèi)容是否為網(wǎng)址的相關(guān)方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-07-07
本篇文章主要是對js中top的作用進行了深入的介紹，需要的朋友可以過來參考下，希望對大家有所幫助2014-03-03
impress.js 是國外一位開發(fā)者受 Prezi 啟發(fā)，采用 CSS3 與 JavaScript 語言完成的一個可供開發(fā)者使用的表現(xiàn)層框架(演示工具)。感興趣的朋友跟著小編一起學(xué)習(xí)吧2015-09-09