惠安县规划建设局网站,wordpress 调用输入,网站建设的目的,网页设计与制作配套素材前面我们分享了关于js使用贪心算法解决找零问题#xff0c;本文我们接着为大家介绍JS基于贪心算法解决背包问题。贪心算法#xff1a;在对问题求解时#xff0c;总是做出在当前看来是最好的选择。也就是说#xff0c;不从整体最优上加以考虑#xff0c;他所做出的仅是在某…前面我们分享了关于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 0var remainCapacity capacityvar 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.weightreturnValue 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相关推荐
