Day 21：贪婪演算法(greedy algorithm)

之前写到过分治法，它并不是单一个演算法，而是许多演算法设计的基础。同理，贪婪演算法也是一种设计模式。这类演算法的作法是，在每一个阶段选择当前最佳解，并以此达到整个问题的最佳解。

举例来说，如果现在有一个空间可以借人使用，我们希望在时间不冲突的情况下，借越多组人越好，收益越多。现在有这些想借的团体和他们提出的时间：

如果利用贪婪演算法来解决这个问题，它的想法就是希望每一段时间都最大程度的利用这个空间(局部最佳解)，这样整天就可以最大程度的利用这个空间(整体最佳解)。以时间的利用来说，演算法的步骤可以是：

1. 第一段借给使用时段最早结束的社团。
2. 借给第一段之後最早结束的社团。

以这样的做法，第一段借给最早结束的围棋社，围棋社後开始并最早结束的是花艺社，花艺社後最早结束的是机器人社。所以一天下来借给最多组人的安排就是围棋社→花艺社→机器人社。

在一些问题中，贪婪演算法就是这麽轻松就可以找到解法。这种演算法有一些特性：

1. 贪婪演算法通常很简单，(同个问题)可以容易设计出一种或多种贪婪演算法。
2. 要分析贪婪演算法的执行时间通常也不难。
3. 大部分贪婪演算法并非永远正确，也就是碰到某些输入时，无法得出预期的最佳解。而且就算一个贪婪演算法是正确的，也很难证明。

第三点可能让人觉得，这麽简单果然有诈！竟然并非永远正确？！我们可以先用背包问题(knapsack problem)来看贪婪演算法可能不正确的例子。

背包问题

如果一间店里有各种价值和重量的东西，我们有一个最多能装三公斤的背包，想知道在不超过背包容量的情况下，如何装进最有价值的物品组合。

用贪婪演算法的话，局部最佳解可以是每一次都装入背包容纳得下、最值钱的东西。

当店里的物品是这样时，可以靠贪婪演算法装入装得下又最值钱的物品A，透过局部最佳解也得到了整体最佳解。

可是当店里的物品如下，用贪婪演算法会装入物品A，可是物品B加物品C却是更值钱的选择。

从这个例子可以看出，有时候贪婪演算法无法得到最佳解，但可以得到还ok的解。

可是如果有那麽多快速又正确的演算法，为什麽还要用这种很可能得不到最佳解的演算法呢？下一回会写到适合使用贪婪演算法的问题和情境。