2 wb it man wb_it_man 于 2016.05.07 20: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个回答

menglanfenghen
menglanfenghen   2016.05.07 22:21
已采纳

求最大受益,思想是把价值最大的先放入依次进行比较,再把价重比最大的进行比较。在比较两者的结果 进行取舍
我以价值最大为例进行比较
第一步:放入w6 w剩=11 n剩=6 p总=18
第二步:放入w2 w剩=6 n剩=5 p总=18+15
第三步:放入w0 w剩=4 n剩=4 p总=18+15+10

第四步:放入w3 因为w3>w剩 当7/4w3 刚好装满 n=3 p总待=18+15+10+7/4*7 = 55.25 待定
第五步:舍弃第四步
放入w4 w剩=3 n=3 p总验=p总=18+15+10+6
第六步 放入w1 w剩=0 刚好装满 n=2 p总验=18+15+10+6+5=54 (验证)
54<55.25
当按照价值最大为例进行比较 最大收益为(1,0,0,7/4,1,1)

    再以价重比最大按照上面的方法进行比较   价重比就是价格除以重量,得出单价进行比较

    结果就是:
    就是10+5*2/3+15+6+18+3=55(1/3)

    55.25<55(1/3)

    所以(x0,x1,x2,x3,x4,x5,x6)=(1,2/3,1,0,1,1,1)

    ps:你的那个注意细节 你把乘号写成加好了,10+5*2/3+15+6+18+3=55(1/3)
wb_it_man
wb_it_man 好的 谢谢
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!