贪婪算法¶
贪婪算法每一步都只会基于当前情况，做出局部最优解，且不会回溯，因此必须保证每一步都是可行的 (feasible) 。只有当局部最优解也是全局最优解时，贪婪算法才能得到正确的结果。
换句话说，贪婪算法的每一步都是做出一个贪婪选择，然后将问题变成一个子问题。我们需要证明的是：
- 贪婪选择性质：总有一个原问题的最优解会包含做出的贪婪选择
- 最优子结构性质：通过将子问题的最优解与做出的贪婪选择结合，可以得到原问题的最优解
活动选择问题¶
给定一系列活动 \(S = \{ a_1, a_2, \cdots, a_n \}\)，这些活动都希望使用某个教室，每个活动的使用时间为 \([s_i, f_i)\)。现希望找到一个最大的活动子集 \(A \subseteq S\)，使得 \(A\) 中的活动之间不会发生时间冲突。
该问题可以通过贪婪算法解决。首先将所有活动按照结束时间 \(f_i\) 递增排序，然后依次选择结束时间最早且不冲突的活动，直到所有活动都被遍历完毕。
可以证明，该贪婪算法的每一步都是最优的，因此最终得到的活动子集 \(A\) 也是最优的。设 \(S_k\) 是一个子问题，\(a_m\) 是 \(S_k\) 中结束时间最早的活动，\(A_k\) 是 \(S_k\) 的一个最优解，\(a_{ef}\) 是 \(A\) 中结束时间最早的活动。这样一来，若 \(f_m = f_{ef}\)，则符合要求，若 \(f_m < f_{ef}\)，则可用 \(a_m\) 替换 \(a_{ef}\)，得到的 \(A_k'\) 仍是最优解，符合要求。
如果每一个活动都有一个权重 \(w_i\)，那么可用动态规划来解决问题。设 \(c_{1, i}\) 为仅考虑从 \(a_1\) 到 \(a_i\) 的最优解，\(k(i)\) 为结束时间在 \(a_i\) 之前且距离 \(a_i\) 最近的不冲突活动，则有状态转移方程：
哈夫曼编码¶
给定一系列要编码的字符，以及它们在文本中出现的次数 \(f_i\)，要求为每个字符提供二进制编码，使得文本所占字节数最少。
我们希望从文本解码时不会产生歧义，这可以通过前缀码实现，即没有任何一个编码是另一个编码的前缀。要构造出这样的编码，可以使用二叉树，具体方法是让每个节点向左儿子的路径代表 0，向右儿子的路径代表 1，然后将字符放在叶子节点上，让从根节点到字符的路径代表其编码。
设每个字符在树中的深度为 \(d_i\)，权重为其频率 \(f_i\)，则编码的代价为 \(\sum d_if_i\)。若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman Tree)。这样，我们的问题就转换为了要构造一颗哈夫曼树。
我们可以通过哈夫曼算法来解决这个问题。每一步，我们都从最小堆中取出权重最小的两个节点，然后新建一个以它们为子节点、它们的权重和为权重的新节点，将其插入最小堆中，直至最小堆只剩一个节点，这最后一个节点的权重即为最后的总代价。该算法的时间复杂度为 \(O(C \log C)\)，下面将证明该算法的解是最优解。
贪婪选择性质：设 \(x\) 和 \(y\) 是字符集 \(C\) 中频率最低的两个字符，\(T\) 是关于 \(C\) 的一个最优二叉树，\(a\) 和 \(b\) 是 \(T\) 中最深的两个叶子节点。我们可以通过将 \(a\) 和 \(b\) 替换为 \(x\) 和 \(y\) 构造一个新的二叉树 \(T'\)，然后显然有 \(\text{Cost}(T') \le \text{Cost}(T)\)，因此 \(T'\) 也是关于 \(C\) 最优的。
最优子结构性质：设 \(x\) 和 \(y\) 是字符集 \(C\) 中频率最低的两个字符，\(C'\) 是 \(C\) 将 \(x\) 和 \(y\) 替换为 \(z\) 后的字符集，其中 \(z.freq = x.freq + y.freq\)，\(T'\) 是关于 \(C'\) 的一个最优二叉树。我们可以通过将 \(z\) 替换为 \(x\) 和 \(y\) 构造一个新的二叉树 \(T\)，通过反证法可以证明，\(T\) 是原问题的最优解：若 \(T\) 不是最优的，则存在 \(T^*\) 使得 \(\text{Cost}(T^*) \lt \text{Cost}(T)\)，由上条性质可得，在 \(T^*\) 中 \(x\) 和 \(y\) 处于最深处，将它们合并得到 \({T^*}'\)，就有 \(\text{Cost}({T^*}') \lt \text{Cost}(T')\)，这与 \(T'\) 是最优的矛盾。