溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

JS基于貪心算法解決背包問題示例

發(fā)布時間：2020-10-05 07:34:38 來源：腳本之家 閱讀：163 作者：Spider--Man 欄目：web開發(fā)

本文實例講述了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ù)學運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設計有所幫助。

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手