贪心算法：
part1: 『样例问题：Barn Repair[1999 USACO Spring Open] 有一长列的牛棚，其中一些需要木板作为屋顶。你可以利用N(N<=50)块木板，任何一块木板都可以覆盖任意长度的牛棚。覆盖所有的必须被覆盖的牛棚并且使覆盖的木板数最少。
主要思想： 贪心算法的最基本思想便是利用小规模的解来得到大规模的解。不像其他的方法。然而，贪心算法只能依赖于所求出的最好的答案。因此，对于样例问题来说，要得到N=5时的答案，必须先求出当N=4时的最好的答案。然后通过这些解去得到N=5时的解。没有一个N=4的解是曾被考虑过的。
问题： 贪心算法有两个基本的问题。（1、如何去构造贪心策略。2、证明贪心算法的正确性。）
如何去构造贪心策略 如何让一个大规模的解从小规模的解里得出？一般来说，这是一个问题的关键。对于样例问题来说，最明显的方法是在四块板到五块板的过程中，挑选一块板，然后去除这一块木板中间的一段，这样就相当于使一块木板变成了两块。你应该选择去除所有木板中有最大的一段覆盖了不需要覆盖木板的牛棚的木板。 为了去除一段已覆盖的牛棚，要选择一块覆盖了那些牛棚的木板，然后将它分成两块：一块覆盖了在分隔段前的牛棚，一块覆盖了在分隔段后的牛棚。
贪心算法的正确性 事实上，真正的挑战在于贪心所得到的解并不一定正确。即使它们看上去得出了样例答案，随机答案，以及任何你能够想到的情况。但如果有一种情况不正确，那么在评测中至少会出现一个（如果不多）错误。 对于样例问题，来看一下上述描述的贪心算法是否正确，考虑如下： 假设答案不包含算法运行时所除去的最大的裂缝（即前文的分隔块），但是去除了比较小的裂缝。通过在最后结合两块木板在两种不同情况下所得到的答案。两种种情况使用的木板一样多，但其中一种却覆盖了更少的牛棚。覆盖更少牛棚的方案更优，所以假设错误，我们应该一直选择去除更大的裂缝。
如果答案不包含这个特殊的裂缝，而包含了另一个和这个裂缝一样大，做了相同变化，使答案也同样。那么这个新的选择也是正确的，我们可以任选一个。 因此，存在一个最佳答案包含了最大裂缝。所以，在每一步中，总存在一个最佳答案是一个最佳选择，从而可知，最终的答案一定是最佳的。
结论 如果贪心算法存在，使用它，他们容易编写，容易调试，运行快速，而且使用更少的内存，在比赛环境中较好地编写一个正确算法。唯一缺少的元素便是正确性。如果贪心算法能够得到正确答案，那么就用它，但不要认为贪心算法适用于所有题目。』
类似问题：
三值排序问题 [IOI 1996]
有一个由N个数值均为1、2或3的数构成的序列（N<= 1000），其值无序，现要求你用最少的交换次数将序列按升序顺序排列。
算法：排序后的序列分为三个部分：排序后应存储1的部分，排序后应存储2的部分和排序后应存储3的部分，贪心排序法应交换尽量多的交换后位置正确的（2，1）、（3，1）和（3，2）数对。当这些数对交换完毕后，再交换进行两次交换后位置正确的（1，2，3）三个数。
分析：很明显，每一次交换都可以改变两个数的位置，若经过一次交换以后，两个数的位置都由错误变为了正确，那么它必定最优。同时我们还可发现，经过两次交换后，我们可以随意改变3个数的位置。那么如果存在三个数恰好为1，2和3，且位置都是错误的，那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质，我们的贪心算法成立。
货币系统 -- 一个反例 [已删节]
奶牛王国刚刚独立，王国中的奶牛们要求设立一个货币系统，使得这个货币系统最好。现在告诉你一个货币系统所包含的货币面额种类（假设全为硬币）以及所需要找的钱的大小，请给出用该货币系统找出该钱数，并且要求硬币数尽量少。
算法：每次都选择面额不超过剩余钱数但却最大的一枚硬币。例如：有货币系统为{1，2，5，10}，要求找出16，那么第一次找出10，第二次找出5，第三次找出1，恰好为最优解。
错误分析: 其实可以发现，这种算法并不是每一次都能构成最优解。反例如：货币系统{1，5，8，10}，同样找16，贪心的结果是10，5，1三枚，但用两枚8的硬币才是最优解。因为这样，贪心的性质不成立，如此解题也是错的。
拓扑排序
给你一些物品的集合，然后给你一些这些物品的摆放顺序的约束，如"物品A应摆放在物品B前"，请给出一个这些物品的摆放方案，使得所有约束都可以得到满足。
算法：对于给定的物品创建一个有向图，A到B的弧表示"物品A应摆放在物品B前”。以任意顺序对每个物品进行遍历。每当你找到一个物品，他的入度为0，那么贪心地将它放到当前序列的末尾，删除它所有的出弧，然后对它的出弧指向的所有结点进行递归，用同样的算法。如果这个算法遍历了所有的物品，但却没有把所有的物品排序，那就意味着没有满足条件的解。