《计算机算法设计与分析》课后练习09

Author:龙箬
Computer Application Technology
Change the World with Data and Artificial Intelligence !
CSDN@weixin_43975035
民不足而可治者，自古及今，未之尝闻

问题描述：
求以下情况下的背包问题的最优解
利用贪心策略求解下列背包问题，设 $n=4$，$M=54$，
$(p_1,p_2,p_3,p_4)=(20,16,10,18)$
$(w_1,w_2,w_3,w_4)=(16,12,15,24)$
求解向量 $X$ 计算 $\sum p_i{x}_i$

解：按 $p_i/w_i$ 非增次序排序可得：
$p_2/w_2=4/3$
$p_1/w_1=5/4$
$p_4/w_4=3/4$
$p_3/w_3=2/3$
其中 $p_2/w_2$，$p_1/w_1$，$p_4/w_4$ 可以完全放入背包
剩余空间 $\Delta M=M-w_2-w_1-w_4=2$
故 $w_3$可放入$\frac{2}{15}$部分，其解向量为$(1,1,\frac{2}{15},1)$
则背包问题的最优解为；
$TheBest=\sum p_i{x}_i=16+20+18+\frac{2}{15}\ast 10=55.333$

参考致谢：
国科大 马丙鹏老师《计算机算法设计与分析》

如有侵权，请联系侵删
需要本实验源数据及代码的小伙伴请联系QQ:2225872659