Question

求大神帮忙背包问题啊

假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30）

Answer 1

w(i)=（35,30,50,60,40,10,25）
p(i)=（10,40,30,50,35,40,30）
p(i) / w(i)=( 2/7, 4/3, 3/5, 5/6, 7/8 ,4, 6/5)
x(i)=(1, 1, 0 ,0 ,1 ,1 ,1)
（求和公式）w(i)x(i0=35*1+30*1+50*0+60*0+40*1+10*1+25*1=140
(求和公式)p(i)x(i)=10*1+40*1+30*0+50*0+35*1+40*1+30*1=155
即背包的最优解是 （1, 1, 0 ,0 ,1 ,1 ,1）
最大收益是155
（大概就是这样吧，不知道有没有计算错误，自己再看一下吧）