算法合集之《部分贪心在信息学竞赛中的应用》

《算法合集之《部分贪心在信息学竞赛中的应用》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、部分贪心思想在信息学竞赛中的应用清华附中高逸涵(gaoyihan@gmaiLcom)【摘要】在某些数据规模非常大的问题当中，我们常常希望使用贪心法解决问题，但是纯粹的贪心在某些情形下会有反例存在。在这些情况下，我们可以采取一种折中的方案——部分贪心。降问题规模降低到较小的范围内以后，再采用其他方法解决。部分贪心【正文】引言贪心在信息学竞赛中，是一种非常重要的思想。一般来说，如果贪心算法町以证明其正确性，那么时间复杂度将远远优于其它算法。但是某些时候，一些看上去十分正确而月•效果明显的贪心，会存在为数不多的一些反例,这时便

2、是部分贪心排上用场的时机，再能保证贪心正确性的前提下，尽最减小待处理问题规模，然后对剩K的小规模问题采用其他方法解决。正文在我们详细介绍部分贪心算法之前，首先要知道一些比较基础的东西：1.什么是贪心法2.贪心法有什么优势和劣势3.什么是部分贪心4.部分贪心算法冇什么优势什么是贪心算法贪心算法，顾名思义，就是贪婪地对问题进行决策，在每一个选择而前，寻找当前看起來是最优的一项决策來继续，这样下去，直到达到最终状态，举一个直观的例了。在如下图屮寻找从S到T的最短路，那么贪心法的决策过程会是这样：1.首先从S找一条最短的路到下一

3、层节点，即S->A2.然后从A找一条最短的路到下--层节点，即A->E3.最后从E到T是唯一的决策。这样，我们得到的路径为S->A->E->T,路径长度为1+4+4=9o当然，这样做显然是不正确的，事实上，冇更短的路径S->B->D->T,路径长度为2+2+2=6贪心法的优势和劣势一个正确的贪心法有着许许多多的优点，比如说思路直接，程序效率高，代码量小，空间消耗小等等。然而不幸的是，对于大多数问题，我们难以找到一个简单可行的贪心思路,即使我们找到一个看上去很正确的贪心思路，我们也需要严格的正确性证明来支持这一思路。这往往

4、给我们直接使用贪心算法带來了巨大的困难。什么是部分贪心很多时候，当我们试图使用贪心算法解决问题，却发现存在种种特殊情况，使得我们的贪心算法会产住一些小的错误，这些特殊情况的普遍特点是，数据规模很小，而我们的贪心思路往往是针对人局设计的，而这些细节上的特殊情况往往会使我们感到无从下手。在这种情况卜，我们可以考虑一种特殊贪心方式，在接近初始状态或者冃标状态的决策中采用搜索或者动态规划这类Hj以保证正确性的算法来处理，而对于中间的状态则采用贪心思想解决。这样平衡了算法的效率和正确性，得到了一个相对理想的结果，这种算法便是部分贪

5、心算法。举一个例子：求函数/(x)=x2+sin(x+(p)的最小值，从总体上来看，这个函数的取值主耍和兀2的取值有关，而sin(x+(p)则起小规模干扰作用，但是如果单纯的取兀彳取最小值的位置却不能得到整个函数的最小值。事实上，取最小值的位置一定在x=0的附近位置。这样，我们贪心地得到了一个最小值x=(),然后在其附近采用枚举法取得真正的最小值。这便是部分贪心算法的一个形彖化的例了。部分贪心算法的优势部分贪心在不影响算法总体复杂度的前提卜将边界上的特殊悄况交给一些可以容易保证正确性的算法解决。可以视为对贪心算法的一个改

6、进和推广。如果说，贪心法的优势是效率高，缺点是应用范I韦I狭小，普通算法应用范I韦I广但是效率低下，那么部分贪心则是综合了两者，使得在正确性和算法效率Z间得到了一个平衡。-•般來说，信息学竟赛需要在规定的时间限制下解决规定的题目，需要算法有很好的正确性和不错的效率。这样，部分贪心算法就是唯一能够在时间效率和正确性的双重限制卜瑕好的解决问题的优秀算法。应用实例及结果这里我们通过三个例题具体分析来讨论部分贪心算法的具体应用形式。例一、骆驼题目大意：有“个人带着X个小包和y个人包准备穿过沙漠。所有人都不愿意徒步旅行，因此需要一

7、些骆驼把他们自己和所有大包小包驮在背上。每匹骆驼可以背的物体只能是下列四种组合Z—(因此不能同时背小包和大包)：不超过3个小包；不超过2个大包；1个人与不超过2个小包；1个人和1个大包。最少需要多少骆驼？问题规模：1<=p<=1000000000,0<=x,y<=1000000000初步分析：当所冇人所带的包的种类确定以后，剩下需要的骆驼数冃可以直接算出來，所以我们需要求的只是有多少个人带人包，多少个人带小包。所以可以很容易得到公式：初2罰{唤兀-2,,0)*血x(y-p+i,O)09—}L3」L2」由于数据规模较大，所

8、以枚举法显然会超时。而直接利用数学公式计算，则由于取整运算符的存在而显得略微存些麻烦，我们考虑用部分贪心法解决该问题。采用部分贪心法：我们换一个角度思考问题：1.当一个人带着小包的时候，一个人带2个小包，而一个不带人的骆驼门J以带3个小包，这样相当于把人当成小包來算。2.当一个人带着人包的时候，一个人带1个人包，而一