电子商务网站建设需要多少钱,网站建设的总结200字,网站目录字典,dw制作简单网站模板下载地址文章目录前言如何理解“贪心算法”#xff1f;贪心算法实战分析1.分糖果2.钱币找零3.区间覆盖内容小结最后说一句#x1f431;#x1f409;作者简介#xff1a;大家好#xff0c;我是黑洞晓威#xff0c;一名大二学生#xff0c;希望和大家一起进步。 #x1f47f;本…
文章目录前言如何理解“贪心算法”贪心算法实战分析1.分糖果2.钱币找零3.区间覆盖内容小结最后说一句作者简介大家好我是黑洞晓威一名大二学生希望和大家一起进步。 本文收录于 算法本专栏是针对大学生、初学算法的人准备解析常见的数据结构与算法同时备战蓝桥杯。 前言
贪心算法是一种非常常见的算法它的简单和高效性使其在实际应用中被广泛使用。
贪心算法的核心思想是在每一步都采取当前状态下最优的选择而不考虑未来可能产生的影响。虽然贪心算法不能保证总是得到最优解但在很多情况下它可以获得很好的结果。
本篇文章将介绍贪心算法的基本概念和一些经典应用以及如何通过贪心算法来解决一些实际问题。希望通过本文的阅读读者可以对贪心算法有更加深刻的理解并能够在实际问题中应用贪心算法来得到更好的解决方案。 让我们暴打贪心算法吧
如何理解“贪心算法”
关于贪心算法我们先看一个例子。
假设我们有一个可以容纳100kg物品的背包可以装各种物品。我们有以下5种豆子每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大我们如何选择在背包中装哪些豆子每种豆子又该装多少呢 实际上这个问题很简单我估计你一下子就能想出来没错我们只要先算一算每个物品的单价按照单价由高到低依次来装就好了。单价从高到低排列依次是黑豆、绿豆、红豆、青豆、黄豆所以我们可以往背包里装20kg黑豆、30kg绿豆、50kg红豆。
这个问题的解决思路显而易见它本质上借助的就是贪心算法。结合这个例子我总结一下贪心算法解决问题的步骤我们一起来看看。
第一步当我们看到这类问题的时候首先要联想到贪心算法针对一组数据我们定义了限制值和期望值希望从中选出几个数据在满足限制值的情况下期望值最大。
类比到刚刚的例子限制值就是重量不能超过100kg期望值就是物品的总价值。这组数据就是5种豆子。我们从中选出一部分满足重量不超过100kg并且总价值最大。
第二步我们尝试看下这个问题是否可以用贪心算法解决每次选择当前情况下在对限制值同等贡献量的情况下对期望值贡献最大的数据。
类比到刚刚的例子我们每次都从剩下的豆子里面选择单价最高的也就是重量相同的情况下对价值贡献最大的豆子。
第三步我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下举几个例子验证一下就可以了。严格地证明贪心算法的正确性是非常复杂的需要涉及比较多的数学推理。而且从实践的角度来说大部分能用贪心算法解决的问题贪心算法的正确性都是显而易见的也不需要严格的数学推导证明。
实际上用贪心算法解决问题的思路并不总能给出最优解。
我来举一个例子。在一个有权图中我们从顶点S开始找一条到顶点T的最短路径路径中边的权值和最小。贪心算法的解决思路是每次都选择一条跟当前顶点相连的权最小的边直到找到顶点T。按照这种思路我们求出的最短路径是S-A-E-T路径长度是1449。 但是这种贪心的选择方式最终求的路径并不是最短路径因为路径S-B-D-T才是最短路径因为这条路径的长度是2226。为什么贪心算法在这个问题上不工作了呢
在这个问题上贪心算法不工作的主要原因是前面的选择会影响后面的选择。如果我们第一步从顶点S走到顶点A那接下来面对的顶点和边跟第一步从顶点S走到顶点B是完全不同的。所以即便我们第一步选择最优的走法边最短但有可能因为这一步选择导致后面每一步的选择都很糟糕最终也就无缘全局最优解了。
贪心算法实战分析
对于贪心算法你是不是还有点懵如果死抠理论的话确实很难理解透彻。掌握贪心算法的关键是多练习。只要多练习几道题自然就有感觉了。所以我带着你分析几个具体的例子帮助你深入理解贪心算法。
1.分糖果
我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃但是糖果少孩子多mn所以糖果只能分配给一部分孩子。
每个糖果的大小不等这m个糖果的大小分别是s1s2s3……sm。除此之外每个孩子对糖果大小的需求也是不一样的只有糖果的大小大于等于孩子的对糖果大小的需求的时候孩子才得到满足。假设这n个孩子对糖果大小的需求分别是g1g2g3……gn。
我的问题是如何分配糖果能尽可能满足最多数量的孩子
我们可以把这个问题抽象成从n个孩子中抽取一部分孩子分配糖果让满足的孩子的个数期望值是最大的。这个问题的限制值就是糖果个数m。
我们现在来看看如何用贪心算法来解决。对于一个孩子来说如果小的糖果可以满足我们就没必要用更大的糖果这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面对糖果大小需求小的孩子更容易被满足所以我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子对我们期望值的贡献是一样的。
我们每次从剩下的孩子中找出对糖果大小需求最小的然后发给他剩下的糖果中能满足他的最小的糖果这样得到的分配方案也就是满足的孩子个数最多的方案。
2.钱币找零
这个问题在我们的日常生活中更加普遍。假设我们有1元、2元、5元、10元、20元、50元、100元这些面额的纸币它们的张数分别是c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付K元最少要用多少张纸币呢
在生活中我们肯定是先用面值最大的来支付如果不够就继续用更小一点面值的以此类推最后剩下的用1元来补齐。
在贡献相同期望值纸币数目的情况下我们希望多贡献点金额这样就可以让纸币数更少这就是一种贪心算法的解决思路。直觉告诉我们这种处理方法就是最好的。实际上要严谨地证明这种贪心算法的正确性需要比较复杂的、有技巧的数学推导我不建议你花太多时间在上面不过如果感兴趣的话可以自己去研究下。
3.区间覆盖
假设我们有n个区间区间的起始端点和结束端点分别是[l1, r1][l2, r2][l3, r3]……[ln, rn]。我们从这n个区间中选出一部分区间这部分区间满足两两不相交端点相交的情况不算相交最多能选出多少个区间呢 这个问题的处理思路稍微不是那么好懂不过我建议你最好能弄懂因为这个处理思想在很多贪心算法问题中都有用到比如任务调度、教师排课等等问题。
这个问题的解决思路是这样的我们假设这n个区间中最左端点是lmin最右端点是rmax。这个问题就相当于我们选择几个不相交的区间从左到右将[lmin, rmax]覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。
我们每次选择的时候左端点跟前面的已经覆盖的区间不重合的右端点又尽量小的这样可以让剩下的未覆盖区间尽可能的大就可以放置更多的区间。这实际上就是一种贪心的选择方法。 内容小结
今天我们学习了贪心算法。
实际上贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法这些算法都用到了贪心算法。 从我个人的学习经验来讲不要刻意去记忆贪心算法的原理多练习才是最有效的学习方法。
贪心算法的最难的一块是如何将要解决的问题抽象成贪心算法模型只要这一步搞定之后贪心算法的编码一般都很简单。贪心算法解决问题的正确性虽然很多时候都看起来是显而易见的但是要严谨地证明算法能够得到最优解并不是件容易的事。所以很多时候我们只需要多举几个例子看一下贪心算法的解决方案是否真的能得到最优解就可以了。
最后说一句
感谢大家的阅读文章通过网络资源与自己的学习过程整理出来希望能帮助到大家。
才疏学浅难免会有纰漏如果你发现了错误的地方可以提出来我会对其加以修改。
