JS基于贪心算法解决背包问题示例
本文实例讲述了JS基于贪心算法解决背包问题。分享给大家供大家参考，具体如下：
贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
寻找最优解的过程，目的是得到当前最优解
部分背包问题：固定容积的背包能放入物品的总最大价值
物品ABCD
价格502206060
尺寸5201012
比率101165
按比例降序尽可能多放入物品
functiongreedy(values,weights,capacity){
varreturnValue=0
varremainCapacity=capacity
varsortArray=[]
values.map((cur,index)=>{
sortArray.push({
'value':values[index],
'weight':weights[index],
'ratio':values[index]/weights[index]
})
})
sortArray.sort(function(a,b){
returnb.ratio>a.ratio
})
console.log(sortArray)
sortArray.map((cur,index)=>{
varnum=parseInt(remainCapacity/cur.weight)
console.log(num)
remainCapacity-=num*cur.weight
returnValue+=num*cur.value
})
returnreturnValue
}
varitems=['A','B','C','D']
varvalues=[50,220,60,60]
varweights=[5,20,10,12]
varcapacity=32//背包容积
greedy(values,weights,capacity)//320
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。