贪心算法: 是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。但贪心算法并不能保证得到全局最优。本实验选择【-1背包问题】,请用贪心算法求解(贪心策略的选择是关键)。
问题如下:有一个背包,背包容量是150kg。现有8个物品,物品大小固定,即不可分割。
要求:尽可能让装入背包中的物品总价值最大,但前提条件是:不能超过总容量150kg。
8件物品的标号、重量、价值如下表所示:
物品 重量 价值
1 35kg 10
2 30kg 40
3 6kg 30
4 50kg 50
5 40kg 35
6 10kg 40
7 25kg 30
8 12kg 25
代码采用了三种策略来实现