展开

关键词

贪心算法如何贪心

在前面学习最短路径和最小生成树的时候,我们发现Dijkstra算法,Prim算法,Kruskal算法都是属于典型的贪心算法应用。 这篇文章就是对于贪心算法的入门介绍 贪心算法 贪心算法(又称贪婪算法)是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 问题所具有的这个性质是该问题可用动态 规划算法贪心算法求解的一个关键特征。 我们通过下面两个例题来看下什么时候选用贪心算法求解。 只要能满足贪心算法的两个性质: 贪心选择性质和最优子结构性质,贪心算法就可以出色地求出问题的整体最优解。即使某些问题,贪心算法不能求得整体的最优解,贪心算法 也能求出大概的整体最优解。

47410

贪心算法

贪心算法:分阶段的工作,在每个阶段做出当前最好的选择,从而希望得到结果是最好或最优的算法贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。 任务调度问题(简单) 这是一个经典简单的贪心问题,只是题目有点长需要认真读。解决这个问题,重点要想好贪心的策略: 阶段性:每个时间表选择哪一个任务。 贪心策略:根据“误时惩罚”对任务进行排序,优先排惩罚大的任务,如果这个时间点已经被占了,依次向前找,判断任务是否能安排? 阶段性:每个区间选择那两个点 贪心策略:   对于所有的区间按右端点从小到大排序。(根据右端点排序)   从第一个区间开始扫描是否覆盖了两个点? 56 */ 最近做了一些贪心算法的题,感觉贪心算法主要是根据问题的要求想出贪心策略,上面提到了没有涉及到什么数据结构和高精度的问题。所以用到最多的就是排序。

32130
  • 广告
    关闭

    腾讯云+社区系列公开课上线啦!

    Vite学习指南,基于腾讯云Webify部署项目。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法(四) 贪心

    贪心算法 例题 1,最大子序和 来自LeetCode 53 解法 1,贪心 根据题意我们可以发现这样一个贪心思想:当前面子序列和小于0时,不如从自身重新开始计算。

    9470

    贪心算法

    http://blog.csdn.net/xywlpo/article/details/6439048 贪心算法的设计思想          贪心算法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择 换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解,但不能总获得整体最优解,通常可以获得近似最优解。 但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。 这是贪心算法可行的第一个基本要素。 贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。       问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 贪心法的应用 哈夫曼编码 0-1背包问题 磁盘文件的存储 生产调度问题 信息查询

    89420

    贪心算法

    贪心算法的基本思想: ------求解最优化问题的算法包含一系列步骤 ------每一部都有一组选择 ------做出当前看来最好的选择 ------希望通过做出局部优化选择达到全局优化选择 - -----贪心算法不一定总产生优化解 ------贪心算法是否产生优化解,需要严格证明 贪心算法产生优化解的条件 ------贪心选择性:若一个优化问题的全局优化解可以通过局部优化选择得到,则该问题成为具有贪心选择性 ------优化子结构 与动态规划方法的比较 ------动态规划方法可用的条件:(1)优化子结构(2)子问题重叠性(3)子问题空间小 ------贪心法可用的条件:(1)优化子结构(2)贪心选择性 这是一种典型的贪心算法,它只顾眼前,但能得到最优解。 (2)部分背包问题。有n个物体,第i个物体的重量为wi,价值为vi,在总重量不超过C的情况下让总价值尽量高。 一种直观的贪心策略是:优先拿“价值除以重量的值”最大的,直到重量和正好为C。

    67920

    贪心算法

    贪婪算法 贪心算法(Greedy Algorithm) 简介贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择 {看着这个名字,贪心,贪婪这两字的内在含义最为关键。 index = i; } } } return index; } 有了物品,有了方法,下面就是将两者结合起来的贪心算法 按照贪心算法的三个步骤:1.41分,局部最优化原则,先找给顾客25分;2.此时,41-25=16分,还需要找给顾客10分,然后5分,然后1分;3.最终,找给顾客一个25分,一个10分,一个5分,一个1分 ^_^;总结:贪心算法的优缺点优点:简单,高效,省去了为了找最优解可能需要穷举操作,通常作为其它算法的辅助算法来使用;缺点:不从总体上考虑其它可能情况,每次选取局部最优解,不再进行回溯处理,所以很少情况下得到最优解

    46411

    贪心算法+回溯算法

    贪心算法 先来比较一下贪心算法和动态规划 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择,不考虑整体,只考虑局部最优,所以它不一定能得到最优解; 动态规划则是每个步骤都要进行一次选择,但选择通常要依赖子问题的解 所以一般选自自底向上自带备忘的机制,所以一定是最优解; 最优子结构的概念 如果一个问题的解包含其子问题的最优解,则称该问题具有最优子结构,也就是求解大问题的解,是通过求解小问题取解决 如果理解了最优子结构,则会发现贪心算法和动态规划都利用了最优子结构的性质 实现该算法的过程 从问题的某一初始解出发 while 能朝给定总目标前进一步 do 求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 典型的可用贪心来解的问题有 最小生成树、分数背包问题( 所以先选择B,再选择A  再从C中选择5   这时价值肯定最大 但贪心算法一开始就说了,并不保证最优解,所以有时会配合随机算法算法导论第三版第五章有讲)使用  一般来说贪心算法的代码比动态规划简单的多 这是解集合树(具体怎么解决这个问题,再分子界限算法中解决,这里只是介绍回溯法本身) ?

    78491

    经典算法贪心算法

    什么是贪心算法?   贪心算法,又称贪婪算法(Greedy Algorithm),是指在对问题求解时,总是做出在当前看来是最好的选择。 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。 贪心算法适用的问题   贪心策略适用的前提是:局部最优策略能导致产生全局最优解。也就是当算法终止的时候,局部最优等于全局最优。 如果确定可以使用贪心算法,那一定要选择合适的贪心策略; 贪心算法的几个例子 1. 经我们分析,这种情况是不适合用贪心算法的,因为我们上面提供的贪心策略不是最优解。

    81130

    常用算法贪心算法

    因而选用贪心算法必须保证当前选的最好的必定是整体最好的。 示例 分发饼干 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 换句话说就是贪心的选择执行n个不一样的任务,使得CPU能够充分利用 要选择先执行的任务,得考虑如何使得当前选择整体是最优的,加入随便选择一个任务A执行,当存在一个任务B它的任务数比选择的任务数要多时,这意味着 list.add(top); for (int i=0;i<maxLength;i++) { //贪心的选择没有执行过的 maxNumsTaskIndex]--; } return maxNumsTaskIndex; } } 复制代码 当然如果只要解决问题,可以直接计算出结果 还是使用贪心的策略来作为逻辑考虑的 }else{ break; } } return Math.max(tasks.length,(taskArr[25]-1)*(n+1)+m); } 复制代码 附录 贪心算法思路

    28320

    贪心算法问题-LeetCode 55、45(贪心算法,跳跃问题)

    贪心算法问题:LeetCode #55 #45 1 编程题 【LeetCode #55】跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置。 算法原理: 遍历整个nums数组,每次计算从i位置的最大可能到达的距离,然后依次更新这个最大值,如果最大值大于nums的大小nums.size(),那么就返回true, 否则返回false. 说明: 假设你总是可以到达数组的最后一个位置 算法原理: 由于题目中规定总能到达数组的最后一个位置,因此我们在遍历数组时每次都要去找最大的跳跃位置,只有到达了这个最远的边界end,我们才让step进行自加

    67260

    贪心算法-LeetCode 134、111(递归算法,异或性质,贪心

    对于swap函数使用中间变量的形式大家都不陌生了,但是对于面试官来说这种方法不出奇,并不是面试官想要的!有没有不使用中间变量的呢? 在swap2函数中,我们可以...

    36720

    贪心算法秘籍

    换言之,贪心算法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。贪心算法能得到许多问题的整体最优解或整体最优解的近似解。因此,贪心算法在实际中得到大量的应用。 那么,贪心算法需要遵循什么样的原则呢? 2.1.2 贪亦有道 “君子爱财,取之有道”,我们在贪心算法中“贪亦有道”。 问题的最优子结构性质是该问题是否可用贪心算法求解的关键。 图2-1 原问题和子问题 2.1.3 贪心算法秘籍 武林中有武功秘籍,算法中也有贪心秘籍。上面我们已经知道了具有贪心选择和最优子结构性质就可以使用贪心算法,那么如何使用呢?下面介绍贪心算法秘籍。 不是贪心算法像冒泡排序,而是冒泡排序使用了贪心算法,它的贪心策略就是每一次从剩下的序列中选一个最大的数,把这些选出来的数放在一起,就得到了从大到小的排序结果,如图2-2所示。 ?

    53620

    算法导论系列:贪心算法(1)

    正文开始: 贪心算法其实本身就跟我们人性一样,看到眼前的好吃的,拿来拿来别客气.但是丝毫不顾忌自己还得燃烧卡路里.贪心算法也是这样. 贪心算法的本质其实就是总是做出当前最好的选择,也就是说算法总是期望通过局部最优选择从而得到全局最优的解决方案. 但是大家想想贪心算法其实是很”目光短浅”的,因为仅仅根据当前眼下的信息来做出决策,这样就不是从整体来最优考虑,他做出的选择只能是某种意义上的局部最优.但是,贪心算法可以得到很多问题的整体最优解或者近似解 ,在实际生活中还是有一定的意义的,因此贪心算法还是得到了广泛的应用. 但是贪心也不是全部都要,贪心算法也是有一定的原则,经过我们很多的实践后发现,要想利用贪心算法解决问题,必须要满足两个性质: 1:贪心选择 所谓的贪心选择其实是说原问题可以分解成一个个的小问题来去求解,

    52120

    算法导论系列:贪心算法(2)

    这篇文章我们将来一起看看贪心算法一个具体例子, Dijkstra算法 Dijkstra算法最著名的应用是解决单元最短路径,这是一类贪心算法,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径 这个算法不仅仅是贪心算法,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围. 现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示: 下图是算法的过程(用电子屏幕写字果然很不舒服): 最终的路径为: 代码如下:

    39610

    算法导论系列:贪心算法(2)

    这篇文章我们将来一起看看贪心算法一个具体例子, Dijkstra算法 Dijkstra算法最著名的应用是解决单元最短路径,这是一类贪心算法,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径 这个算法不仅仅是贪心算法,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围. 下图是算法的过程(用电子屏幕写字果然很不舒服): ? ? 最终的路径为: ? 代码如下: ? 运行结果: 1:输入样例 ? 2:输出结果 ? 下一篇文章我们将一起学习下哈夫曼编码

    44830

    贪心算法举例分析

    本文链接:https://blog.csdn.net/qq_27717921/article/details/52946572 贪心算法和动态规划的不同之处 在动态规划方法中每个步骤都要进行一次选择, 我们也可以自顶向下的求解,但需要备忘机制,当然,即使算法是自顶向下进行计算,我们仍然需要的先求解子问题在进行选择。 在贪心算法中,我们总是做出当时看来最佳的选择然后求解生下的唯一的子问题。 贪心算法进行选择时可能依赖之前做出的选择但不依赖任何将来的选择或者是子问题的解。因此,与动态规划先求解子问题才能进行第一次选择不同,贪心算法在进行第一次选择之前不求解任何的子问题。 贪心算法在每一步都做出当时看起来最佳的选择,也就是说它总是做出局部最优的选择,希望这样的选择能导致全局最优,但是并不能保证得到最优解。 最小生成树算法、单源最短路径的Dijkstra算法都是贪心算法策略设计的算法。 活动选择问题。每个任务都有一个开始时间Si和一个结束时间Fi,其中对单个的活动来说,它的结束时间要大于开始时间。

    26310

    贪心算法:合并区间

    局部最优可以推出全局最优,找不出反例,试试贪心。 那有同学问了,本来不就应该合并最大右边界么,这和贪心有啥关系? 有时候贪心就是常识! } return result; } }; 时间复杂度:O(nlogn) ,有一个快排 空间复杂度:O(1),不算result数组(返回值所需容器占的空间) 总结 对于贪心算法 跟着「代码随想录」刷题的录友应该感受过,贪心难起来,真的难。 那应该怎么办呢? 正如我贪心系列开篇词关于贪心算法,你该了解这些! 中讲解的一样,贪心本来就没有套路,也没有框架,所以各种常规解法需要多接触多练习,自然而然才会想到。 「代码随想录」会把贪心常见的经典题目覆盖到,大家只要认真学习打卡就可以了。 就酱,学算法,就在「代码随想录」,值得介绍给身边的朋友同学们! 打算从头开始打卡的录友,可以在「算法汇总」这里找到历史文章,很多录友都在从头打卡,你并不孤单! ? -------end-------

    37310

    贪心算法:跳跃游戏

    可以看一下公众号左下角的「算法汇总」,「算法汇总」已经把题目顺序编排好了,这是全网最详细的刷题顺序了,方便录友们从头打卡学习,「算法汇总」会持续更新! ❞ 55. 「贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点」。 局部最优推出全局最优,找不出反例,试试贪心! 如图: ? 一些同学可能感觉,我在讲贪心系列的时候,题目和题目之间貌似没有什么联系? 是真的就是没什么联系,因为贪心无套路! 没有个整体的贪心框架解决一些列问题,只能是接触各种类型的题目锻炼自己的贪心思维!

    20520

    相关产品

    • 抗量子签名服务

      抗量子签名服务

      腾讯云抗量子签名服务(PQSS)是一项能够抵抗量子计算攻击和传统计算攻击的签名服务。其是一款面向量子时代的安全产品,具备更高计算效率和更低资源消耗。

    相关资讯

    热门标签

    扫码关注云+社区

    领取腾讯云代金券