摘要: 0/1背包问题有好几种贪婪策略,每个贪婪策略都采用多步过程来完成背包的装入,在每一步过程中利用贪婪准则选择一个物品装入背包。
1、从剩余的物品中,选出可以装入背包的价值最大的物品。利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。例如,n=2, weight=[100, 10, 10], prize=[20, 15, 15], count=105。当利用价值贪婪准则时,获得的解为x= [1, 0, 0],这种方案的总价值为20。而最优解为[0, 1, 1],其总价值为30。
……
阅读全文