JS基於貪心演算法解決背包問題

前面我們分享了關於js使用貪心演算法解決找零問題，本文我們接著為大家介紹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

相關推薦：

##JS如何使用貪心演算法解決找零問題

php實作貪心演算法0-1背包問題

Java如何實作背包演算法的實例分析

以上是JS基於貪心演算法解決背包問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！