本文實例講述了JS基于貪心算法解決背包問題。分享給大家供大家參考，具體如下：

貪心算法：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

尋找最優解的過程，目的是得到當前最優解

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

物品 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

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

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