Greedy Algorithm
新手翻译 jiajie999 校对yapinglu
Sample Problem: Barn Repair [1999 USACO Spring Open]
贪心算法
例题: 栅栏修理[Barn Repair 1999 USACO Spring Open]
------------------------------------
There is a long list of stalls, some of which need to be covered with boards. You can use up to N (1 <= N <= 50) boards, each of which may cover any number of consecutive stalls. Cover all the necessary stalls, while covering as few total stalls as possible.
农场有一排牛棚，其中的一些牛棚需要用一些木板覆盖起来。你最多可以用N(1<=N<=50)块木板，每个都能覆盖任何数目的，连续的牛棚。现在你要 覆盖所有需要覆盖的牛棚，而且使覆盖的牛棚的数目尽可能得少。
-------------------------------------
The Idea
The basic idea behind greedy algorithms is to build large solutions up from smaller ones. Unlike other approaches, however, greedy algorithms keep only the best solution they find as they go along. Thus, for the sample problem, to build the answer for N = 5, they find the best solution for N = 4, and then alter it to get a solution for N = 5. No other solution for N = 4 is ever considered.
Greedy algorithms are fast, generally linear to quadratic and require little extra memory. Unfortunately, they usually aren't correct. But when they do work, they are often easy to implement and fast enough to execute.
思路：
贪心法的基本思想是用局部解构造全局解，不象其它方法，贪心法在求解过程中只保留所找到的最优解。以此例题来说，构造N=5的最优解，就先要找到N=4的解,改变其后用它得到N=5的解.其它N=4时的解都不予考虑。
贪心法的特点是速度快,通常是线性到二次式，不需要多少额外的内存. 不幸的是，它们通常是不正确的。不过当它们能正确工作时，贪心法是容易实现和执行的.
--------------------------------------
Problems
There are two basic problems to greedy algorithms.
How to Build
How does one create larger solutions from smaller ones? In general, this is a function of the problem. For the sample problem, the most obvious way to go from four boards to five boards is to pick a board and remove a section, thus creating two boards from one. You should choose to remove the largest section from any board which covers only stalls which don't need covering (so as to minimize the total number of stalls covered).
To remove a section of covered stalls, take the board which spans those stalls, and make into two boards: one of which covers the stalls before the section, one of which covers the stalls after the second.
贪心法的两个基本问题
如何建立？
怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。以本例题来说,用4块板的解构造5块板的解，最明显的方法就是找一块木板然后去掉一段,这样从一块产生两块。我们应该选择去掉任何不需要用来覆盖牛棚的那一块板上最大的一段（这样就可以使得覆盖的牛棚数目最小）。
去掉一段覆盖的牛棚，把涉及到这些牛棚的那块板分成两块，一块覆盖在这段前面的牛棚，另一块覆盖着对豁免的那些牛棚。
---------------------------------------------------------
Does it work?
The real challenge for the programmer lies in the fact that greedy solutions don't always work. Even if they seem to work for the sample input, random input, and all the cases you can think of, if there's a case where it won't work, at least one (if not more!) of the judges' test cases will be of that form.
这样做可以吗？
对编程者来讲最大的挑战就是贪心法得到的解并不总是正确的。即使所得到的解似乎对例子中的输入，随机输入，以及你能想到的所有情形都正确，只要有一种情形不适合，那么考官的测试情况一定包括了这正情形。
-----------------------------------------------------------
For the sample problem, to see that the greedy algorithm described above works, consider the following:
对于例子中的问题，下面来看一下前面讲的贪心法是怎呢回事：
----------------------------------------------------------
Assume that the answer doesn't contain the large gap which the algorithm removed, but does contain a gap which is smaller. By combining the two boards at the end of the smaller gap and splitting the board across the larger gap, an answer is obtained which uses as many boards as the original solution but which covers fewer stalls. This new answer is better, so therefore the assumption is wrong and we should always choose to remove the largest gap.
假设我们的解里没有包含由该算法去掉的一个大的空隙，却包含了相对小的空隙。我们通过把位于小空隙末端的那两块板合并，同时将跨越大空隙的那块板分开的方式，就可以得到一个与原来的解用同样数目的木板但又覆盖更少的牛棚的解。这个新的解是更好的,所以这个假设是错误的，我们总是应该选择去掉最大的空隙。
-----------------------------------------------------------
If the answer doesn't contain this particular gap but does contain another gap which is just as large, doing the same transformation yields an answer which uses as many boards and covers as many stalls as the other answer. This new answer is just as good as the original solution but no better, so we may choose either.
如果解不包含这一个空隙但包含另一个一样大的空隙，使用同样的方法，我们会得到一个与原来的解用了同样数目的木板而且覆盖了同样数目的牛棚的解。新解与原解相同，我们可以选任何一个。
-------------------------------------------------------
Thus, there exists an optimal answer which contains the large gap, so at each step, there is always an optimal answer which is a superset of the current state. Thus, the final answer is optimal.
因此存在一个包含最大空隙的最优解,而且每步总有一个包含了当前状态的最优解。所以最终的解是最优的。
----------------------------------------------------
Conclusions
If a greedy solution exists, use it. They are easy to code, easy to debug, run quickly, and use little memory, basically defining a good algorithm in contest terms. The only missing element from that list is correctness. If the greedy algorithm finds the correct answer, go for it, but don't get suckered into thinking the greedy solution will work for all problems.
结论：
如果贪心解存在就是用它。贪心法编码容易，调试方便，运行迅速，使用内存少，这些确定了它不失为在竞赛中的一个优秀算法。这里唯一没有提到的要素是它的正确性。如果用贪心算法能找到答案，就用它。不要以为贪心算法可以用于任何问题而浪费大量时间。