贪心算法也是用来解决最优解问题
它在每一步都做出当时看起来最佳的选择，未必有动态规划严谨，但是在某些问题中，确实可以得到最优解。在一些 NP 完全问题中，贪心算法也可以被用来得到近似最优解
活动选择问题
问题的定义为：给出一组活动的开始和结束时间，选出一个最大的兼容活动子集
这个问题具有最优子结构：一个问题的最优解由一个分割点元素和左右两个子问题的最优解组成，遍历分割点的选择，即可写出动态规划方法的核心公式
贪心策略：选出与当前已选集兼容的“结束时间最早的活动”（这里有点绕，结束时间最早是因为，序列是按结束时间升序排列的，所以就按顺序检查选择第一个兼容的活动即可）
可以证明此问题用贪心算法可以得到一个最优解：定理 16.1
可以用递归或迭代两种方式实现这个算法，时间性能都为 O(n)，再次印证了一个道理：我们用递归来分析问题，用循环来解决问题
贪心算法原理
再次明确了一个概念，最优子结构：将一个问题做出一种划分，如果划分后得到的几个问题的最优解组合起来就是原问题的一个最优解，那么这种划分就是一个最优子结构
设计贪心算法的步骤：
1.将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。（限定划分的形式：选择 + 一个子问题）
2.证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。（意思是原问题总是存在一个最优解包含贪心策略做出的选择）
3.证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
贪心选择性质：我们可以通过做出局部最优选择来构造全局最优解。
最优子结构，贪心算法通常使用更直接的最优子结构（意思就是贪心选择加一个子问题）
贪心算法与动态规划的比较：
0-1 背包问题适合动态规划
分数背包问题用贪心算法更佳
总体来说，贪心算法的效率优于动态规划，不需要计算太多的重叠子问题
赫夫曼编码
变长编码思想是，赋予高频字符短码字，赋予低频字符长码字
前缀码：没有任何码字是其它码字的前缀的编码（非常奇葩的名字）
构造一颗树，将出现频率越高的字符放在离根结点越近的地方，这棵树可以用来编码和解码
赫夫曼编码的方法是：将队列中频率最低的两个结点合成一颗子树，子树的频率为两个结点的频率之和，将子树放回队列中。循环处理队列直至只剩一个结点。
赫夫曼编码的性能主要受最小优先队列操作的性能影响。使用最小二叉堆时，总运行时间为 O(nlgn)
引理 16.2 和引理 16.3 证明了赫夫曼编码的正确性
赫夫曼编码的贪心选择：在每个步骤可选的所有合并操作中，赫夫曼选择是代价最小的那个
拟阵和贪心算法
拟阵的概念比较抽象，阅读了额外的文章帮助理解：
http://www.voidcn.com/article/p-dxllptii-bcv.html
坦白的说，这一节和下一节的内容基本是由关于拟阵的各种引理、定理及其证明组成的，阅读起来有一定的难度，其大略思想如下：
1.拟阵是一个数学概念，它包含一些性质，可以证明贪心算法得到的解是拟阵问题最优解。
2.如果我们可以将一个问题抽象为拟阵，并能证明问题符合拟阵的性质，那么就可以用贪心算法解决这个问题。
用拟阵求解任务调度问题
任务调度问题是指，单处理器上的一组任务，每个任务有一个截至时间及错过时间后的惩罚值，问题的最优解是使总惩罚值最小的任务序列。
解决任务调度问题的步骤是，先证明任务调度问题可以抽象为拟阵，然后用贪心算法求得最优解。
