国家集训队2008-论文集部分贪心在信息学竞赛.docVIP

部分贪心思想在信息学竞赛中的应用 清华附中 高逸涵 (gaoyihan@) 【摘要】在某些数据规模非常大的问题当中，我们常常希望使用贪心法解决问题，但是纯粹的贪心在某些情形下会有反例存在。在这些情况下，我们可以采取一种折中的方案——部分贪心。降问题规模降低到较小的范围内以后，再采用其他方法解决。 【关键字】 部分贪心 【正文】 引言 贪心在信息学竞赛中，是一种非常重要的思想。 一般来说，如果贪心算法可以证明其正确性，那么时间复杂度将远远优于其它算法。 但是某些时候，一些看上去十分正确而且效果明显的贪心，会存在为数不多的一些反例，这时便是部分贪心排上用场的时机，再能保证贪心正确性的前提下，尽量减小待处理问题规模，然后对剩下的小规模问题采用其他方法解决。 正文 在我们详细介绍部分贪心算法之前，首先要知道一些比较基础的东西： 什么是贪心法 贪心法有什么优势和劣势 什么是部分贪心 部分贪心算法有什么优势 什么是贪心算法 贪心算法，顾名思义，就是贪婪地对问题进行决策，在每一个选择面前，寻找当前看起来是最优的一项决策来继续，这样下去，直到达到最终状态，举一个直观的例子。在如下图中寻找从S到T的最短路，那么贪心法的决策过程会是这样： 首先从S找一条最短的路到下一层节点，即S-A 然后从A找一条最短的路到下一层节点，即A-E 最后从E到T是唯一的决策。 这样，我们得到的路径为S-A-E-T，路径长度为1+4+4=9。 当然，这样做显然是不正确的，事实上，有更短的路径S-B-D-T，路径长度为2+2+2=6 贪心法的优势和劣势 一个正确的贪心法有着许许多多的优点，比如说思路直接，程序效率高，代码量小，空间消耗小等等。然而不幸的是，对于大多数问题，我们难以找到一个简单可行的贪心思路，即使我们找到一个看上去很正确的贪心思路，我们也需要严格的正确性证明来支持这一思路。这往往给我们直接使用贪心算法带来了巨大的困难。 什么是部分贪心 很多时候，当我们试图使用贪心算法解决问题，却发现存在种种特殊情况，使得我们的贪心算法会产生一些小的错误，这些特殊情况的普遍特点是，数据规模很小，而我们的贪心思路往往是针对大局设计的，而这些细节上的特殊情况往往会使我们感到无从下手。 在这种情况下，我们可以考虑一种特殊贪心方式，在接近初始状态或者目标状态的决策中采用有哪些信誉好的足球投注网站或者动态规划这类可以保证正确性的算法来处理，而对于中间的状态则采用贪心思想解决。这样平衡了算法的效率和正确性，得到了一个相对理想的结果，这种算法便是部分贪心算法。 举一个例子：求函数的最小值，从总体上来看，这个函数的取值主要和的取值有关，而则起小规模干扰作用，但是如果单纯的取取最小值的位置却不能得到整个函数的最小值。事实上，取最小值的位置一定在x=0的附近位置。这样，我们贪心地得到了一个最小值x=0，然后在其附近采用枚举法取得真正的最小值。这便是部分贪心算法的一个形象化的例子。 部分贪心算法的优势 部分贪心在不影响算法总体复杂度的前提下，将边界上的特殊情况交给一些可以容易保证正确性的算法解决。可以视为对贪心算法的一个改进和推广。 如果说，贪心法的优势是效率高，缺点是应用范围狭小，普通算法应用范围广但是效率低下，那么部分贪心则是综合了两者，使得在正确性和算法效率之间得到了一个平衡。 一般来说，信息学竞赛需要在规定的时间限制下解决规定的题目，需要算法有很好的正确性和不错的效率。这样，部分贪心算法就是唯一能够在时间效率和正确性的双重限制下较好的解决问题的优秀算法。 应用实例及结果 这里我们通过三个例题具体分析来讨论部分贪心算法的具体应用形式。 例一、骆驼 题目大意： 有p个人带着x个小包和y个大包准备穿过沙漠。所有人都不愿意徒步旅行，因此需要一些骆驼把他们自己和所有大包小包驮在背上。每匹骆驼可以背的物体只能是下列四种组合之一（因此不能同时背小包和大包）：不超过3个小包；不超过2个大包；1个人与不超过2个小包；1个人和1个大包。最少需要多少骆驼？ 问题规模： 1=p=1000000000, 0=x,y=1000000000 初步分析： 当所有人所带的包的种类确定以后，剩下需要的骆驼数目可以直接算出来，所以我们需要求的只是有多少个人带大包，多少个人带小包。 所以可以很容易得到公式： 由于数据规模较大，所以枚举法显然会超时。而直接利用数学公式计算，则由于取整运算符的存在而显得略微有些麻烦，我们考虑用部分贪心法解决该问题。 采用部分贪心法： 我们换一个角度思考问题： 当一个人带着小包的时候，一个人带2个小包，而一个不带人的骆驼可以带3个小包，这样相当于把人当成小包来算。 当一个人带着大包的时候，一个人带1个大包，而一个不带人的骆驼可以带2个大包，这样相当于把人当成大包来算。 显然，一般来说，把