首页 > 其他 > 详细

有一个背包,容量为m,然后有n个货物,重量分别为w1,w2,w3...wn,每个货物的价值是v1,v2,v3...vn,w和v没有任何关系,请求背包能装下的最大价值

时间:2019-02-15 12:46:03      阅读:1609      评论:0      收藏:0      [点我收藏+]

优先塞入单位重量下价值最高的货物

 1 var maxLoad = 15;
 2     var loads = [5, 6, 2, 1, 9, 3, 5]
 3     var prices = [4, 2, 5, 3, 2, 6, 7]
 4     function maxValue(arr, m, load, price) {
 5       console.log(arr, m, load, price)
 6       for (var i = 0; i < arr.length - 1; i++) {
 7         if (arr[i].load + load > m) {
 8           return price
 9         } else if (arr[i].load + load === m) {
10           return arr[i].price + price
11         } else {
12           arr.splice(0, 1)
13           maxValue(arr, m, arr[i].load + load, arr[i].price + price)
14         }
15       }
16     }
17     function maxPrice(m, load, price) {
18       var singlePrices = []
19       for (var i = 0; i < load.length - 1; i++) {
20         singlePrices.push({
21           single: prices[i]/loads[i],
22           load: loads[i],
23           price: prices[i]
24         })
25       }
26       var priceQuene = singlePrices.sort(function(a, b) {
27         return b.single - a.single
28       })      
29       return maxValue(priceQuene, maxLoad, 0, 0)
30     }
31     console.log(maxPrice(maxLoad, loads, prices))

 

有一个背包,容量为m,然后有n个货物,重量分别为w1,w2,w3...wn,每个货物的价值是v1,v2,v3...vn,w和v没有任何关系,请求背包能装下的最大价值

原文:https://www.cnblogs.com/codejoker/p/10382705.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!