算法设计与分析第四章思维导图 贪心

贪心这一章寒假学算法基础课的时候没好好听，没怎么学证明，导致学算法课的时候从0开始学。等下周没事了好好学一下，太菜了。

1.活动安排问题 给定n个活动[l,r]，在不冲突的前提下，如何安排更多的活动?  按照区间右端点排序，然后能选则选。 贪心选择: 最优子结构: 2.最优装载 给定重量上限c，n个箱子重量wi,装入尽可能多的箱子。   按照重量从小到大排就完了。 贪心选择: 最优子结构: 3.霍夫曼编码 经典问题.优先队列维护最小值 证明huffmancode问题等价于证明最优前缀码。 贪心选择: 每次选最小的两个，不妨设x和y是频率最小的两个字符，等价于存在最优前缀码使得x和y具有相同码长且仅最后一位编码不同。也就是x和y是最深叶子且互为兄弟。 证明: 假设x和y不是最深叶子，那么b和c是最深叶子且互为兄弟。 f(x)