【算法1-3】贪心算法
贪心算法的含义
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
简单举例说明
最最简单的举个例子:我有n张纸币,然后你要拿出10张纸币,使得相加最大,那么大家都会选择从大到小拿10张纸币,这样相加一定是最大的。这可以说是贪心算法的一种体现。
但是大家发现没有,这个方法是我们看到之后立马想到的,没有经过严谨证明的,当然大家会觉得这个很简单的问题,干嘛还要证明呢?
很多情况下,在类似的算法题中,我们都会有种想当然的情况,有些时候贪心确实是对的,但是有些时候你的想当然可能就是错的。
所谓贪心算法的证明主要就是在求得局部最优解,在我的理解中就是,在可能出现的任何情况下,贪心一点不会得到坏的结果,那么贪心往往就是最优解。
拿之前的例子举例,我不抽10张最大的纸币,我就随机抽10张,这种情况下,如果抽出来的10张中没有最大面值的纸币,这时候我用最大面值的纸币代替其中最小的那张,这样的策略是使得最后相加变大的,即便原先就有最大面值,无法代替,但是没有代替也没有使得最后的结果变糟糕,只是平了罢了。
所以,如果在可能出现的任何情况下,贪心一点不会得到坏的结果,那么贪心往往就是最优解
难一点的例子说明
背包问题:有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
这个问题答案也很明显,既然物品可以分割成任意大小,要使得装入背包中的物品总价值最大,那么肯定会先装(价值/质量)最大的物品吧。简单来说就是,同样的质量,要使得其价值最大,就是使得其单位价值最大。
大家可能会想,那这样的话凡是都贪心一下好像不是不可,但其实这个贪心有点靠感觉,就是往往你遇到贪心的题就知道要用贪心算法了。
大家可以想一下,同样是前面的背包问题,去掉“物品可以分割成任意大小”这句话的话,这个题目还可以用贪心吗?
是不能的,举个极端例子,只有两个货物能装进背包里,其他五个质量都大于150,第一个货物质量是2,总价值是22;第二个货物质量是149,总价值是1490,按照贪心算法的话,那么得出的答案就是22,因为贪心算法认为要先装单位价值最大的货物,但是很明显我可以直接装第二个货物,这样价值就是1490了。所以这样的话这题就不是用贪心的,是用动态规划的,动态规划我们之后再讲了
所以,是否要使用贪心算法是要证明的,不是想当然的,如何证明贪心呢,就是一句话,在在可能出现的任何情况下,贪心一点不会得到坏的结果,那么贪心往往就是最优解。
简单说几句话
贪心算法是真的有点感觉的意思,就是你要先感觉到了它是贪心,然后再去证明它是不是,当然,有些大佬一眼就能看出来,做题多的当然是有点好处的。
可能大家会觉得太简单了,这里放一道题吧,P1080 [NOIP2012 提高组] 国王游戏 https://www.luogu.com.cn/problem/P1080
最近这一个月状态都不是很好,学习也没心思学,因为脚上长了两个鸡眼,做了一次小手术也没好,跑步也疼,没有精神,感觉自己要变成肥宅了,但是我觉得这样不好,人还是要阳光一点的。
上次蓝桥杯省赛我拿了一等奖,感觉运气好,当然我也有努力的,这是真话耶,当然信不信由你们了。