贪心算法详解

在预算内合理安排行程，不要贪心游览过多地方。 #生活知识# #旅游生活# #旅游预算#

      贪心算法又叫贪婪算法（greedy algorithm），是一种基于分治思想的求解“最优解”的算法。至于为什么打上双引号，请听我慢慢道来。

      其实贪心算法在生活中应用十分广泛，最常举的例子就是找钱的问题。如果从找的总张数最小的角度考虑：想找26块钱，正常的方式就是20，5，1。这就是明显的贪心方法：每次选择符合当下条件最大的。但这个也不是一定的，再举个例子：假如有面值4元，3元，1元的钞票，目标是6元。按照贪心算法来看会选择4，1，1。可是从直觉很清楚的看出来3，3是更好的选择。所以贪心算法也不是适用于所有情况的。下面就来分析一下，什么时候适合，什么时候不适合吧！

       在分析之前，咱们再聊聊贪心算法本身，以增强对它的了解。前文说过贪心算法基于分治的思想，也是把问题分为若干个子问题，再联合求解。前文既然说贪心算法可以求解“最优解”问题。那这个看起来和动态规划很相似啊！（老师说过绝对相同的东西，是绝对不会起两个名字的！！！）下面就来聊聊贪心算法和动态规划的区别：

      从某种程度上看，贪心算法是一种特殊情况下的动态规划。动态规划和贪心算法都是要去求解局部最优解，也就是说两个的子结构都是最优子结构，并且都要求有无后效性。之前的文章介绍过，动态规划的方向是自下而上。每层最优解选自上一层的很多最优解。但贪心算法更多的是自上而下，每层选择当前最好的，不断缩小问题的规模。比如上文举的找钱问题，每次都拿面值最大的，这样剩下需要找的数量值就越来越小。简单点说动态规划每层里有很多个最优解，从而确保了下一层得到的仍然是最优解。贪心算法就是只管当前层选择出最优解就进入下一层。万事有利有弊：这个特点导致贪心算法计算的比动态规划更快，但也有可能导致不是最优解的情况。

      刚才提了一个特别专业的词：无后效性。上网查了有关的资料，对此的理解加深一步。就是当前状态确定之后，之后所做的决定与之前所做的决定没有一点关系。在网上看到一篇博客，举了个例子解释的很清楚，并且对相同例子做了有后效性和无后效性的对比，网址附于文末。

      从以上的分析，不难看出，贪心算法适用于那些具有最优子结构但是无后效性的情况。常举的例子（包括我们的课本）都举了Dijkstra算法（求解单源最短路径）、Kruskal算法（求解最小生成树）、Prim算法（求解最小生成树）。（网上有很多文章讲它们是什么，我说的没有人家好，再次不再赘述）。那有一个问题来了：为什么它们适合呢？

       这三个算法都有一个特点：找最小。在每轮的迭代中都会选择一个最小的值。满足了“贪心”的条件。而且每次迭代过程中，会对当前数据进行一次更新，更新过后就不再和之前的数据有任何关联了，满足了无后效性。

      在使用贪心算法的时候，为了达到最优子结构，要选择贪心策略。我原来的观点就是认为“多”，越多越好。但是我学习过后，发现贪心策略也不是唯一的，也有好几种“多”，下面结合一个例子来进行介绍（以下例子摘选自一篇blog，网址附于文末）：

【背包问题】有一个背包，容量是M=150，有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品：A B C D E F G

重量：35 30 60 50 40 10 25

价值：10 40 30 50 35 40 30

分析：

目标函数： ∑pi最大

约束条件是装入的物品总质量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占重量最小的物品装入是否能得到最优解？

（3）每次选取单位重量价值最大的物品，成为解本题的策略

      可以清楚的发现，三种方法都是一种贪心策略，都遵循“多”的原则。第一种让每种的价值最“多”，第二种让能装的数量最“多”，第三种让装的单位重量价值最“多”。将这个三种贪心策略进行实际运算比较，就会发现第三种是本例真正的最优解。由此可见，贪心策略的选择也会大大影响到是否是最优解。

      贪心算法看起来不错，但更多还是要动手实践（此处diss自己的手懒）。因为自己的水平有限，如果要错误的地方，请各位高手再下方评论区及时指正，谢谢！

背包问题参考网址：https://www.jianshu.com/p/ab89df9759c8link

无后效性参考网址：https://blog.csdn.net/qq_30137611/article/details/77655707link

网址：贪心算法详解 https://www.yuejiaxmz.com/news/view/765750

相关内容

贪心算法详细讲解（附例题，一看就会）
人生快乐法则：贪心算法
Nearth==>贪心算法
购物打折优惠的计算方法详解
优化算法综述
动滑轮省力计算方法详解
递归算法详解
经典与现代的优化算法详解
超详细！动态规划详解分析（典型例题分析和对比，附源码）
详解个性化推荐五大最常用算法

随便看看