前面我們分享了關(guān)于js使用貪心算法解決找零問題，本文我們接著為大家介紹JS基于貪心算法解決背包問題。

貪心算法：在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。尋找最優(yōu)解的過程，目的是得到當(dāng)前最優(yōu)解。

部分背包問題：固定容積的背包能放入物品的總最大價(jià)值

物品 A B C D

價(jià)格 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)推薦：

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的背包问题 贪心算法 java_JS基于贪心算法解决背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。