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

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

1、部分贪心在信息学竞赛中的应用北京市清华附中高逸涵引言引入众所周知，贪心算法是一个在信息学竞赛中应用广泛的高效算法。但是有的时候，由于小规模针对性数据的存在，使得贪心算法不能得到正确的结果。如何解决这一问题呢？部分贪心，顾名思义，就是在问题的局部采用贪心算法，而在其他部分采用其他算法。部分贪心引言为什么要“部分”贪心？当问题的特殊情况普遍较小的时候，对于边界数据采用其他算法处理可以有效的回避特殊情况的讨论。部分的普通算法对于总体时间复杂度影响并不大。部分的贪心可以极大的提高算法的时间效率。引言举个例子

2、：我们要最优化目标函数为了求得目标函数的最小值，我们可以首先贪心的求出趋势函数的最小值，然后在其左右寻找目标函数的最小值。例题[例题1]骆驼[例题2]CowRelays[例题1]骆驼有p个人带着x个小包y个大包穿越沙漠每匹骆驼可以背的物体只能是下列四种组合之一：不超过3个小包；不超过2个大包；1个人与不超过2个小包；1个人和1个大包。问最少需要多少骆驼？数据范围：1<=p,x,y<=1000000000[例题1]骆驼首先，当所有人所带的包的种类确定以后，剩下需要的骆驼数目可以直接算出来。所以我们需要

3、求的只是有多少个人带大包，多少个人带小包。很容易得到如下公式：(p,x,y分别为人,小包,大包数)但由于数据规模巨大，直接枚举显然行不通，需要另想办法。[例题1]骆驼由于取整运算符的存在，导致直接数学计算变得比较困难。但是从整体趋势上来看，i的增加显然有利于ans的减小。那么按照贪心思想，我们需要尽量让人带着小包。[例题1]骆驼我们很容易得到一个贪心算法：如果当前小包的个数>=2并且还有人是空闲的，那么令这个人带着小包，否则令这个人带大包。很不幸，这个算法是错误的(x=3,y=3,p=1)。如何改进

4、？正确性？部分贪心！[例题1]骆驼当人数和小包的数量都充分大的时候，令人带小包显然是没错的。经过验证，人数和小包数>=20的时候，一定存在一个最优解使得存在一个骆驼带着人和小包。算法的正确性采用调整法很容易证明。而当人数和小包数有一个小于20时，可以采用枚举法解决问题。[例题1]骆驼已知朴素算法贪心算法解答大规模数据小规模特例部分贪心算法xx[例题2]CowRelays在一个无向图中有T条边，每个点至少和两条边相连，每条边有一个长度，询问从给定起点到给定终点的包含N条边的路最短是多长。数据规模：1<

5、=N<=1000000000,1<=T<=100[例题2]CowRelays首先看到这一题目，我们的直观感受是，最优解一定是这样的一条路经：首先从起点运动到某一个点上。然后在这个点所连接的最小边上往复运动。最后从这个点直接运动到终点。针对这一思想，我们很容易设计出一个贪心算法——枚举一条边做往复运动，然后从起点和终点分别向这条边走增量最短的路径到达。[例题2]CowRelays所谓增量最短路径，就是将所有边减去基准边之后得到的新图内的最短路径。ST5555477N=20基准边311113[例题2]C

6、owRelays这样的贪心算法的复杂度为，但是运用部分贪心算法避免重复计算，可以将复杂度进一步降为算法瓶颈在于对于每条边，我们都要求一次最短路，我们希望在一次中解决所有最短路问题。[例题2]CowRelays回顾我们求最短增量路径的过程，显然，我们所求的最短增量路径一定是在边数确定时的最短路径。因此，我们只需要用动态规划预处理出源点到每一个点所走边数一定时所得的最短路径的长度，然后在贪心时枚举最短增量路径长度即可。部分贪心思想！[例题2]CowRelaysST5555477N=20N/A71015…

7、…基准边323SuvTSuvTSuvT[例题2]CowRelays贪心算法：朴素动态规划：部分贪心：快快快慢慢慢优势互补！结果[例题1]骆驼时间复杂度效果贪心算法O(1)WrongAnswer朴素算法O(N)TimeLimitExceed部分贪心算法O(1)Accepted结果[例题2]CowRelays时间复杂度效果倍增算法较慢贪心算法较慢朴素算法很慢部分贪心算法很快总结朴素算法——思路简单，算法低效，不易出错贪心算法——思路复杂，算法高效，易出错部分贪心——思路简单，算法高效，不易出错取长补短，

8、优势互补集两家之所长，自成一体ThankYou!例题1正确性证明假设当有至少20个小包和20个人时，存在最优解使得没有骆驼带着人和小包。则至少有6个骆驼只带着小包，20个骆驼带着大包和人。那么将4个带着小包的骆驼和6个带着大包和人的骆驼重分配，这时我们有12个小包，6个大包，6个人，我们只需令6个骆驼带着人和小包，3个骆驼带着大包，这样只需要9个骆驼即可，即我们得到了一个比最优解更优的解，矛盾，因此假设不成立。关于和以前论文之间的关系楼天城前辈在2004年有过一篇论文