摘要: 0/1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入，在每一步过程中利用贪婪准则选择一个物品装入背包。

1、从剩余的物品中，选出可以装入背包的价值最大的物品。利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，n=2, weight=[100, 10, 10], prize=[20, 15, 15], count=105。当利用价值贪婪准则时，获得的解为x= [1, 0, 0]，这种方案的总价值为20。而最优解为[0, 1, 1]，其总价值为30。
……

  阅读全文