有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）
正确答案:
可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
由于8>5，所以不能再放进背包。
结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。
1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
由于8>5，所以不能再放进背包。
结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。
答案解析:有
微信扫一扫手机做题