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

更多关于javascript相关内容感兴趣的读者可查看本站专题：《javascript数据结构与算法技巧总结》、《javascript数学运算用法总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》

希望本文所述对大家javascript程序设计有所帮助。