一本通提高篇学习笔记-贪心算法

开启新的啃书之旅。

贪心算法对我来说其实并不陌生。无论是在之前做过的水题中,还是在先前的热身赛和新生赛中,都有贪心算法的运用。前几天我校mhr大佬也为大家讲解了一些贪心算法的运用,这次我再结合一下书上的东西,也许就当一次复习吧。


贪心算法

它是一种求解最优化问题的常用算法。与其说它是一种算法,倒不如说它是一种思想更为合适。在众多的算法中,贪心算法可以算是最接近人们日常思维的一种算法。

比较抽象的来说,就是从问题的初始状态出发,通过若干次的贪心选择而得到最优值的一种策略。换句话说,贪心策略是一种在每次决策时采取当前意义下的最优策略的算法,它只能满足局部最优,但是是否能满足全局最优则并不一定。这主要取决于问题的最优解是否包含全部的局部最优解。

简单来讲,就是哪个最能满足当下的需求就选哪个。比如新生赛上alice和bob那个题。

题目大意:有n堆糖果,数量可能不同,Alice和bob轮流拿糖果直到全部拿完。
保证总是Alice先拿糖果,而且这两个人绝顶聪明,最后谁的糖果多谁获胜。
Alice获胜输出A Bob获胜输出B 平局输出again

在这个问题里面,alice和bob每次的选择一定是最对他们有利的。那么什么才是最有利的?显然,它们会照着最大的取,这样每次都选择当前最大的堆,最后能保证答案的最大化。可以想出,如果中间有任何一个环节取走的不是最大值,那么显然最后的结果一定不是所有可能里面最大的结果,那么也就不满足“绝顶聪明”这个设定了。

当时我是这样想的:(具体请见原文)

思路:两个人拿糖果自然是哪一堆最多就拿哪个,这样是对自己最有利的。所以这题考场上我直接采用了贪心思想,所以先对所有的糖果堆从大到小排个序,然后Alice拿第一大,Bob拿第二大,Alice拿第三大……如此循环往复,可以看出Alice永远拿奇数堆,Bob永远拿偶数堆,然后统计一下这俩人最后能拿到的总糖数对比一下就是结果了。

贪心算法的特点

贪心选择。所谓贪心选择是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,而后的每一步都是当前看似最佳的选择,这种选择只依赖于已作出的选择,而不依赖于未作出的选择。

执行算法时,每一次得到的结果都是当前局部的最优解,但只有满足全局最优解包含局部最优解时,才能保证贪心算法正确。此规律常用来证明贪心算法的正确性。

(实际上,在考场上几乎不会给你证明贪心正确性的时间,所以如果想到贪心算法的话,可以尝试举几个反例,如果实在举不出来,就可以基本判定贪心正确)

简单的贪心实例

最优装载问题

给定n个物品,第i个物品重量为wi,选择尽量多的物体,使得总重量不超过C。

只需要考虑物体的重量,那么显然按着轻的装能够保证装的物体最多,也就是选择尽量多的物品。所以排个序,从轻到重挨个装就好,一直到全部装完(所有物品重量和加起来不够C或者直到装不下)。

部分背包问题

给定n个物品,第i个物品重量为wi,价值为vi。在重量不超过C的前提下让价值最大,价值与重量成比例。

这里就不能只简简单单考虑物品的重量或者价值了,我们应该考虑把性价比最大化,才能保证既装的又多,价值又高。所以先预处理一下所有物品,把所有物品的性价比列出来,对性价比进行排序,然后按照性价比从大到小依次装,直到装不下或者全装上都不到C。

值得注意的是,在这个问题里是不存在装不下下一个东西后背包有剩余空间的情况的。因为物品可以只选择一部分。所以一直到装不下那个物品之前,之前的物品必然是全部装上的,这也是贪心思想的一种体现。

乘船问题

有n个人,第i个人的重量为wi,每艘船的载重量为C,且每艘船最多只能载两个人。求用最少的船装下所有人的方案。

最早mhr讲到这个问题的时候,我这个sb是这样想的:

把所有人的人分成两部分,一部分是重量大于C/2的,另一部分是重量小于C/2的,然后这些重量大的自己乘一艘船,重量小的两人一艘船。

但是很快,这个算法被我自己否决了。如果有两个或更多的人的体重极小,以至于船上站上一个体重大于C/2的人还能再让他们上那几条船,那么这个答案就不正确了。

这个正常的贪心算法比较巧妙。它试图让最轻的人和最重的人配对。

大意是这样,先考虑最重的人和最轻的人,如果这俩人加起来重量超过C,那么说明这个体重比较重的人是一定不可以和任何一个其他人同乘一条船的。所以他要自己一条船,此时继续向后找体重第二大,第三大……分别与最小体重的人放在一块看一下重量是不是大于C,一直找到第一个两人加起来不大于C的组合。此时之前找过的那些人一定是无法和其他任何人同乘一条船的。所以这些人的数量直接就计入答案的一部分。在剩下这些人里面,由于最重的和最轻的都可以同乘一条船,那显然剩余的组合(就是第二重与第二轻,第三重与第三轻……)都可以同乘一条船(想一想,为什么)。

最后答案的话,假设找出那些只能一人一条船的人后剩下的人数为k,那么最终答案就是:(n - k) + k / 2 (k是偶数),奇数的话再在这个结果下+1就好。

应用——区间问题

本部分随着题解一并整理吧233333


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:一本通提高篇学习笔记-贪心算法

文章作者:Shawn Zhou

发布时间:2018年12月09日 - 19:12

最后更新:2019年01月18日 - 19:01

原始链接:http://shawnzhou.xyz/2018/12/09/18-12-09-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。