也许你想成为太阳，可你却只是一颗星辰；也许你想成为大树，可你却是一棵小草。于是，你有些自卑。其实，你和别人一样，也是一片风景：做不了太阳，就做星辰，在自我的星座发光发热；做不了大树，就做小草，以自我的绿色装点期望……
本文实例讲述了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程序设计有所帮助。
到此这篇关于JS基于贪心算法解决背包问题示例就介绍到这了。你不能决定生命的长短，但你可以控制它的质量；你不能左右天气，但你可以改变心情；你不能改变容貌，但你可以展现笑容；你不能控制他人，但你可以掌握自己；你不能预知明天，但你可以掌握今天；你不能样样胜利，但你可以事事尽心。更多相关JS基于贪心算法解决背包问题示例内容请查看相关栏目，小编编辑不易，再次感谢大家的支持！
