【算法•日更•第三期】最贴切的贪心算法讲解

朴灿烈づ我的快乐病毒、 2021-12-01 10:04 227阅读 0赞

▎敢问此间贪心为何物？

☞『引入』

在平时我们在解决一些事情时都会用到贪心的思想，我可以实诚的告诉你，你可能已经会贪心了。

比如说，在我们买东西时，同种物品绝对是买便宜的那一家的货啦，比如说西红柿如果一家卖1元/斤，那么你肯定不会买1.2元/斤的。

再比如说：你正在打游戏，假如突然天上掉下了一个箱子，那么给你一个选择，你要一个装着大师剑的箱子，还是要一个装着一个烂大街的小木棍的箱子，当然，你一定会选择前者。

如果你会这样做，那么，恭喜你，你已经学会贪心了。

☞『贪心算法』

贪心算法（又称贪婪算法）是指，在对[问题求解][Link 1]时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部[最优解][Link 2]。（copy自百度）

说白了就是无论什么情况下都要取当前最优的方法，比如说我要去学校，假如学校在南面，那么我一定会向南走，否则都会绕远。

☞『计算机实例』

![1551435-20190706143142330-791039198.png][]

如上图所示，这是一个有6个格子的方格阵，要求从每列中取出一个数，使总和最大。

显然，这道题是可以贪心的，只要取每列中的最大的数就可以了。

▎这么简单为什么不用？

☞『引入』

![1551435-20190706143814627-1378778078.png][]

如上图所示，这是三块苹果，按大小分为了大块、中块、小块，那么咱们来做一个游戏：不限时间，一共三块，每吃完一块后可以接着吃剩下的，那么比比谁吃得多。

按照贪心的思路来说，绝对拼手速先吃到大块，接下来呢？剩下啥吃啥呗。

但是如果用动态规划的思路的话，我会先吃小块，无论对方吃中块还是大块，都会赶在他吃完前拿走剩下的第三块（如果这也比不过，你直接认怂就行了），显然，任意两块都会比一块多。

☞『贪心不一定是最优的』

由上面生活中的例子可以看出，贪心每次只选择当前最优的方案，却不在乎这个选择对整个大问题是否最优，显然，对于这个问题来说这是不正确的。

这正是贪心与动态规划的不同。

☞『一个正常的例子』

还是之前的图：

![1551435-20190706160449147-1433589290.png][]

但是题变了，现在我要从左下角走到右上角，求走过路径上的最大值。

要求：

1）走过的格子不能再走；

2）只能向上或向右；

贪心算法求解：1 -> 3 -> 4 -> 6 。

![1551435-20190706161126353-408978767.png][]

动态规划求解：1 -> 2 -> 10 -> 6 。

![1551435-20190706161205379-1603462758.png][]

显然动态规划的解才是最优的，而贪心却不是。

▎怎样才能贪心？

☞『贪心选择』

贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。（copy自百度）

一句话概括这一堆(tuo)话：就是说必须得让每一次的选择都得是当前最优的。

☞『最优子结构』

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题 。（copy自百度）

一句话概括这一堆(tuo)话：就是说这道题必须得保证每一次的当前最优选择对于全局来说都是最优的。

--------------------

因此，只有同时满足贪心选择和最优子结构的题才能用到贪心。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11142693.html

[Link 1]: https://baike.baidu.com/item/%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/6693186
[Link 2]: https://baike.baidu.com/item/%E6%9C%80%E4%BC%98%E8%A7%A3/5208902
[1551435-20190706143142330-791039198.png]: /images/20211201/f1982d1196be41ab96564bf63f204a4d.png
[1551435-20190706143814627-1378778078.png]: /images/20211201/2c00cbd00cd94d8fa1e08576182da8f1.png
[1551435-20190706160449147-1433589290.png]: /images/20211201/4d57b714e7c548e8a97fe0df06489467.png
[1551435-20190706161126353-408978767.png]: /images/20211201/d9935d9f60c9473db4c5ad80d1a8a6fe.png
[1551435-20190706161205379-1603462758.png]: /images/20211201/52c45d04eb5640749c8b5d941e1fc469.png