3.7.5 为什么说贪婪算法并不是解决问题的最优方案

还是看“装箱”问题，以说明贪婪算法并不是解决问题的最优方案。该算法依次将物品放到第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。设n件物品的体积按从大到小排序，即有V0≥V1≥…≥Vn−1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。

再看下面的例子：假设有6件物品，它们的体积分别为60、45、35、20、20和20单位体积，箱子的容量为100单位体积。按上述算法计算，需要3只箱子，各箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子装物品6。但最优解为两只箱子即可，分别装物品1、4、5和2、3、6。这个例子说明，贪心算法不一定能找到最优解。