欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

JS基于贪心算法解决背包问题

程序员文章站 2022-04-26 08:11:30
...
前面我们分享了关于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基于贪心算法解决背包问题的详细内容,更多请关注其它相关文章!