摘要: 0/1背包問題有好幾種貪婪策略,每個貪婪策略都采用多步過程來完成背包的裝入,在每一步過程中利用貪婪準則選擇一個物品裝入背包。
1、從剩余的物品中,選出可以裝入背包的價值最大的物品。利用這種規則,價值最大的物品首先被裝入(假設有足夠容量),然后是下一個價值最大的物品,如此繼續下去。這種策略不能保證得到最優解。例如,n=2, weight=[100, 10, 10], prize=[20, 15, 15], count=105。當利用價值貪婪準則時,獲得的解為x= [1, 0, 0],這種方案的總價值為20。而最優解為[0, 1, 1],其總價值為30。
……
閱讀全文