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

来源：动视网责编：小OO 时间：2020-11-27 20:10:30

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

贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。寻找最优解的过程，目的是得到当前最优解。部分背包问题：固定容积的背包能放入物品的总最大价值。物品 A B C D。价格 50 220 60 60。尺寸 5 20 10 12。比率 10 11 6 5。按比例降序尽可能多放入物品。

推荐度：

点击下载本文 文档为doc格式

导读贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。寻找最优解的过程，目的是得到当前最优解。部分背包问题：固定容积的背包能放入物品的总最大价值。物品 A B C D。价格 50 220 60 60。尺寸 5 20 10 12。比率 10 11 6 5。按比例降序尽可能多放入物品。

前面我们分享了关于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基于贪心算法解决背包问题

推荐度：

点击下载本文 文档为doc格式

标签：贪心算法背包问题 js基于贪心算法解决背包问题

热门焦点

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

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

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

最新推荐

猜你喜欢

热门推荐