Greedy Algorithm

贪心算法

译 by Lucky Crazy & Felicia Crazy 样例：牛棚修理 [1999 USACO 春季公开赛]

Farmer John 有一列牛棚，在一次暴风中，牛棚的一整面墙都被吹倒了，但还好不是每一间牛棚都有牛。Farmer John 决定卖木料来修理牛棚，然而，刻薄的木材提供商却只能提供有限块的木料（木料的长度不限），现在告诉你关着牛的牛棚号，和提供的木材个数N，你的任务是编程求出最小的木块长度和。（1 <= N <= 50） 贪心思想：

贪心思想的本质是每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。例如：在样例中，若已经发现 N = 5 时的最优解，那么我们可以直接利用 N = 5 的最优解构成 N = 4 的最优解，而不用去考虑那些 N = 4 时的其他非最优解。

贪心算法的最大特点就是快。通常，二次方级的存储要浪费额外的空间，而且很不幸，那些空间经常得不出正解。但是，当使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。 贪心的难点：

贪心算法有两大难点： 如何贪心：

怎样才能从众多可行解中找到最优解呢？其实，大部分都是有规律的。在样例中，贪心就有很明显的规律。但你得到了 N = 5 时的最优解后，你只需要在已用上的5块木板中寻找最靠近的两块，然后贴上中间的几个牛棚，使两块木板变成一块。这样生成的 N = 4 的解必定最优。因为这样木板的浪费最少。同样，其他的贪心题也会有这样的性质。正因为贪心有如此性质，它才能比其他算法要快。 贪心的正确性：

要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。一个你想出的贪心性质也许是错的，即使它在大部分数据中都是可行的，你必须考虑到所有可能出现的特殊情况，并证明你的贪心性质在这些特殊情况中仍然正确。这样经过千锤百炼的性质才能构成一个正确的贪心。

在样例中，我们的贪心性质是正确的。如下：

假设我们的答案盖住了较大的空牛棚连续列，而不是较小的。那么我们把那部分盖空牛棚的木板锯下来，用来把较小的空牛棚连续列盖住，还会有剩余。那么锯掉它们！还给木材商！同时我们的解也变小了。也就是说，我们获得更优的解。所以，靠盖住较大空牛棚连续列的方法无法获得最优解，我们也应该尽量贪心那些距离小的木板合并。

如果仍有一个空牛棚连续列与我们的答案盖住的那个相同，我们同样使用上述的方法。会发现获得的新解与原解相同，那么不论我们选哪个，结果都将一样。 由此可见，如果我们合并的两块木板间距离最短，那么总能获得最优解。所以，在解题的每一步中，我们都只需要寻找两块距离最小的木板并合并它们。这样，我们获得的解必定最优。 结论：

如果有贪心性质存在，那么一定要采用！因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，它是所有算法中最好的。但是应该注意，别陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好还是不要冒险，因为还有其他算法会比它要保险。 类似问题：

三值排序问题 [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，那么贪心地将它放到当前序列的末尾，删除它所有的出弧，然后对它的出弧指向的所有结点进行递归，用同样的算法。如果这个算法遍历了所有的物品，但却没有把所有的物品排序，那就意味着没有满足条件的解。

Checker Challenge

跳棋的挑战

译 by Jeru

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行，每列，每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。

列号

1 2 3 4 5 6

------------------------- 1 | | O | | | | |

------------------------- 2 | | | | O | | |

------------------------- 3 | | | | | | O |

------------------------- 4 | O | | | | | |

------------------------- 5 | | | O | | | |

------------------------- 6 | | | | | O | |

-------------------------

上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6 列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请遍一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出，这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号将被无警告删除