Greedy Problem¶
Activity Selection Problem¶
有一些活动，每个活动有一个开始时间 \(s_i\) 和结束时间 \(f_i\)，只有一个资源，每个活动占用资源，问最多能安排多少个活动。
按照 \(s_i\) 排序。
Dynamic Programming¶
设 \(c_{i}\) 为活动集合 \(\{a_1, a_2, \cdots, a_i\}\) 的中最多能安排的活动数。则有
其中 \(j\) 为最后一个 \(f_j \leq s_i\) 的活动。
Greedy Algorithm¶
从前往后扫描，每次选择不冲突的最早结束的活动。
加权活动选择问题
每个活动有权重，要求最大化权重。
使用动态规划求解。
区间调度问题
所有活动必须举办，求最少需要多少资源。
先按照开始时间排序，初始资源数量为 1，每次如果所有活动都冲突，则资源数量加 1，否则加入到不冲突的活动中。
Huffman Coding¶
给定一组字符 \(C\) 及其频率，构造一个二叉 Trie，使得期望编码长度最短。
每次选择频率最小的两个字符构造一个新字符，频率为两者之和，直到只剩一个字符。
Proof
Lemma
若 \(x, y\) 是 \(C\) 中频率最小的两个字符，则存在一个最优前缀编码，使得 \(x, y\) 的编码长度相同，且只有最后一位不同。
将 \(x, y\) 和最深的两个叶子节点交换，得到的期望编码长度不会增加。
Lemma
将 \(x, y\) 替换为一个新字符 \(z\)，频率为 \(x, y\) 之和，其上的 Trie 树为 \(T'\)，那么将 \(T'\) 中 \(z\) 替换为 \(x, y\)，得到的是原字符集的一个最优前缀编码树 \(T\)。
设 \(E(T)\) 为 \(T\) 的期望编码长度，则 \(E(T) = E(T') + f_x + f_y\)。
假设存在 \(T''\) 为原字符集上的前缀编码树，使得 \(E(T'') < E(T)\)，那么将 \(T''\) 中 \(x, y\) 合并为 \(z\)，得到 \(T'''\)，有
与 \(T'\) 为最优解矛盾。
综上两个 Lemma 得到 Huffman 编码的正确性。