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

Question

问题：设有背包问题实例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）

Answer 1

求最大受益，思想是把价值最大的先放入依次进行比较，再把价重比最大的进行比较。在比较两者的结果 进行取舍
我以价值最大为例进行比较
第一步：放入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）