wb_it_man
wb_it_man
2016-05-07 12:50

贪心法 背包问题 一道简单的实际问题 不知道大难如何计算出来的。

问题:设有背包问题实例n=7,M=15(背包载重),(w0,w1,...,w6)=(2,3,5,7,1,4,1),
物品装入背包的收益为:(p0,p1,p2,p3,p4,p5,p6)=(10,5,15,7,6,18,3).
求这一实例的最优解和最大收益
答案:最优解:(p0/wo,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(10/2,5/3,15/5,7/7,6/1,18/4,3/1)
(x0,x1,x2,x3,x4,x5,x6)=(1,2/3,1,0,1,1,1)

最大收益:10+5+2/3+15+6+18+3=55(1/3)

我想问加粗斜体的这个答案是怎么求出来的?有公式还是什么思想?
如果按照上一步直接计算答案应该是(5,1.667,3,1,6,4,5,3)

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答