19-算法解析及优化拓展

2.3.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：该算法的时间主要耗费在将宝物按照性价比排序上，采用的是快速排序，算法时间复杂度为O(nlogn)。

（2）空间复杂度：空间主要耗费在存储宝物的性价比，空间复杂度为O(n)。

为了使 m 重量里的所有物品的价值最大，利用贪心思想，每次取剩下物品里面性价比最高的物品，这样可以使得在相同重量条件下比选其他物品所得到的价值更大，因此采用贪心策略能得到最优解。

2．算法优化拓展

那么想一想，如果宝物不可分割，贪心算法是否能得到最优解？

下面我们看一个简单的例子。

假定物品的重量和价值已知，如表2-5所示，最大运载能力为10。采用贪心算法会得到怎样的结果？

| 物品i | 1 | 2 | 3 | 4 | 5 | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | 重量w[i] | 3 | 4 | 6 | 10 | 7 | | 价值v[i] | 15 | 16 | 18 | 25 | 14 | | 性价比p[i] | 5 | 4 | 3 | 2.5 | 2 |

如果我们采用贪心算法，先装性价比高的物品，且物品不能分割，剩余容量如果无法再装入剩余的物品，不管还有没有运载能力，算法都会结束。那么我们选择的物品为 1和2，总价值为 31，而实际上还有 3 个剩余容量，但不足以装下剩余其他物品，因此得到的最大价值为31。但实际上我们如果选择物品2和3，正好达到运载能力，得到的最大价值为34。也就是说，在物品不可分割、没法装满的情况下，贪心算法并不能得到最优解，仅仅是最优解的近似解。

想一想，为什么会这样呢？

物品可分割的装载问题我们称为 背包问题 ，物品不可分割的装载问题我们称之为 0-1背包问题 。

在物品不可分割的情况下，即0-1背包问题，已经不具有贪心选择性质，原问题的整体最优解无法通过一系列局部最优的选择得到，因此这类问题得到的是近似解。如果一个问题不要求得到最优解，而只需要一个最优解的近似解，则不管该问题有没有贪心选择性质都可以使用贪心算法。

想一想，2.3节中加勒比海盗船问题为什么在没有装满的情况下，仍然是最优解，而0-1背包问题在没装满的情况下有可能只是最优解的近似解？