贪心算法是什么？：
?
产生优化解的条件可以和动态规划类比。动态规划要求的是优化子结构（也就是母问题优化解包括子问题优化解）和子问题重叠，贪心则在优化子结构外要求要有“贪心选择性”。什么叫贪心选择性呢？：
这话说的像没说一样，我们还是接着看吧。
动态规划和贪心的关系：
?
可用贪心算法，可能子问题不重叠；子问题重叠了，正确的方法可能不是眼前最好的情况。?
因此，我们要如何证明一个贪心算法呢？：
?前两步解决“能不能用贪心算法”的问题，最后一步解决“是不是贪心算法”的问题。
接下来是一个例题：
?
现在，我们开始进行仔细地定义：
?
要素察觉：总事件集是S,ai事件的开始时间是si,结束时间是fi,(start,finish)，最大集不唯一。
现在我要开始简化问题了：
?
Sij就是在i,j事件之间的符合要求（也就是数量最多不从突）事件的集合。
看好了，现在我要分解问题了：
?假如我要按照常规解法，我应该这样：
?也就是：S(i,j)中间有很多事件，有些其实不在S(i,j)里面（也就是最好的安排里没有这个事件），每个都试一下，看那个最大那个是在S(i,j)里面，也就是正确的分法。但我是贪心算法，我要贪心一点。：
我每次都选最开头的那个在S(i,j)里面结束的， 思路其实就是“我要留下最多的时间给活动，所以尽早结束”
a1肯定选，a2就不一定了，毕竟她有可能是“拦腰截断”的那种类型，S1n+1的第一个结束的事件不一定是a2,a2可能连正式的S(i,j)的门都进不去。
接下来我们来研究一下哈弗曼编码。你可能说我晓得怎么解呀，最常见的放上面，再按照顺序一个一个而往下排呀。现在我们要知道为什么可以这样操作。：
?
?
记得“不能是前缀”这个要求吧？我们之前用二叉树解这个问题也是一样的原因。
现在我们也有一个编码二叉树，不过我们先忘掉之前的解法，假装不知道每个叶子代表什么：
?
那代价要怎么表示呢？：
?
现在就是要代价尽可能小了：
?
图穷匕见，贪起来了。那我们接下来要怎么办？首先是要证明有优化子结构，再是贪心选择性（也就是证明贪心结果就是最佳结果）
?
母树的规律对子树起作用，优化子结构出现了。
?
?思路是：先用贪心算法写出树来，在证明任何与此不同的树都是不好的树，就可了：
因此最后就是这样：?
?
?
?伪代码如下：
堆是上大下小左小右大的二叉树（大小可以颠倒）和我们的需求一致。?