本篇文章给大家谈谈贪心算法，以及贪心算法的基本思想对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、什么是贪心算法？
• 2、贪心算法缺点
• 3、贪心算法总结
• 4、五大常用算法之一：贪心算法
• 5、程序员算法基础——贪心算法
• 6、贪心算法

什么是贪心算法？

贪心算法的基本思想就是分级处理。

贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。

贪心算法可解决的问题通常大部分都有如下的特性：

1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

5、最后，目标函数给出解的值。

贪心算法缺点

贪心算法缺点：

不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。这算法不懂得深谋远虑，自然可能走不到最好的结果啦。

贪心算法的优点：

优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用。

贪心算法基本步骤：

步骤1：从某个初始解出发；

步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；

步骤3：将所有解综合起来。

贪心算法总结

做了这10道题，其实发现贪心算法没有什么规律，要说有什么共同特点就是都是由局部最优从而推出全局最优，每个题基本上都要考虑其局部最优是什么，其全局最优是什么，所以虽然都用到了贪心算法的思想，但是题与题之间又没有什么规律可言。

现在把这10道题的思路总结一下（总结主要以我的主观看法在写，可能别人看会不知道我在说什么）

1.分发饼干：

思路：想要完成最多的小孩满足，那么就得最小的饼干给胃口最小的小孩

这里的贪心思想，

局部最优就是尽可能让一个饼干喂饱一个

全局最优就是最多的小孩满足

2.摆动序列：

思路：这里要找到最长的摆动序列，那么其实就是找那些波峰波谷，如图所示

可以看出来，在到达波峰波谷的路上有几个数字不会影响什么，可以直接去掉。

那么这里的局部最优就是把单调坡上的点删掉，保留最多的波峰波谷

全局最优就是得到对多的波峰波谷，即最长的摆动序列

3.最大子序和

这道题显然可以暴力解出来，即列出所有子序和，找出最大的，不过计算量会比贪心大很多。

这里主要介绍贪心解的思想：

想要得到最大子序和，就得保证每次相加时，相加后不能为负数，因为负数继续往下加一定是拉低总和的，那么我们当加成到负数时就重新从下个数开始加，并实时记录最大的子序和，这样一遍循环就能得出最大子序和。

局部最优：加成负数就立刻停止，并从下个元素重新开始

全局最优：得到最大子序和

4.买卖股票的最佳时机II

思路：想要得到最大利润，那就要低价买入高价卖出，那么怎样的买卖才能得到最大利润呢。

这里就体现出贪心算法的“贪”字（我猜的），这道题贪在哪呢，贪在只要有利可图就去做，即只要今天买入的价钱比明天卖出的价钱底，即有利可图，那么我就去做，做就是在今天买入，在明天卖出。

局部最优：得到每天的最大正利润

全局最优：得到最大利润

5.跳跃游戏

思路：每个数组的元素代表的是可以跳的最远下标，那么我们只要使那个最远下标包含最后一个下标就是可以跳到，那么我们每跳到一个位置就要更新那个可以跳的范围，即可以跳到的最远下标。

局部最优：每次跳跃都得出最远的跳跃范围

全局最优：最后能跳到的最大范围

6.跳跃游戏II

思路：这道题要得到最小的跳跃数，其实只要保证跳的是位置是可以跳范围内更新最远范围的位置就可以了。

为什么这么说呢？以题例来说：

我们刚开始在‘0’的位置，我们能跳到‘1’和‘2’的位置，那么我们怎么跳呢？可以看到跳到‘1’之后更新的最大范围是‘4’，跳到‘2’之后更新的最大范围是‘3’，所以我们就跳‘2’了，因为跳‘1’之后更新的最大可跳范围更大包含了跳‘2’的最大可跳范围，那么肯定是跳‘3’最优呀，这里就体现了局部最优的思想。

局部最优：每次跳后，更新的最大可调范围最大

全局最优：跳跃次数最少

7.K次取反后最大化的数组和

思路：想要得到最大数组和，我们就可以想到怎样做呢？

一，尽可能保证负数最少

二，负数绝对值大的优先变正

三，正数绝对值小的优先变负，有零变零

本着这三条原则做，就能做出来。

那么这道题体现了什么贪心思想呢？

我感觉，前面那三条都是贪心中‘贪’的体现

在负数中，局部最优就是：绝对值大的负数优先变正

在正数中，局部最优就是：绝对值小的正数变负，有零变零

得到的全局最优：数组和最大

8.加油站

思路：首先可以想到这道题是可以暴力解出来了，即分别以每个加油站为起点，得出可以跑一圈的加油站

那么贪心思想做，该怎么做呢，首先可以想到，如果以一个1点为起点当跑着跑着跑到3，油变为负数时，那么说明以这个起点是不行的，但是以2或3为起点行不行呢？答案肯定是不行的，因为1跑到3，油变为负，说明1~3的gas=0的，所以可以得出，如果1~3油数变为负数，那么由2~3油数肯定也为负数。

所以这里就可以得出，如果经过几个加油站油数变为负了，那么起点就更新为这一段路的下个加油站跑

局部最优：油量一旦为负，就从下个加油站重新跑

全局最优：得出可以跑一圈的加油站起点

9.分发糖果

思路：每个孩子至少一个，如果一个孩子比他旁边的孩子优秀，就要比他旁边的糖果多，这道题一旦两边都考虑很容易顾此失彼，所以我们就定义两个循环，分别从左到右，从右到左去考虑，只要更优秀则比他旁边的多1，如果已经多了就不用变了。

局部最优：保证优秀的孩子比他旁边的孩子糖果多

全局最优：满足题中条件，至少要发的糖果

10.柠檬水找零

思路：我们在找零时要遵守的规则一定是：

5 得5

10 得10减5

15 得15，优先减一个10减一个5  如果10块没有则减三个5

局部最优：以最少用的5块的方式找零

全局最优：得到找零能否进行下去

五大常用算法之一：贪心算法

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如， 求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法 。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

可惜的是，它需要证明后才能真正运用到题目的算法中。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：

贪心策略：选取价值最大者。反例：

W=30

物品：A B C

重量：28 12 12

价值：30 20 20

根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。

（3）贪心策略：选取单位重量价值最大的物品。反例：

W=30

物品：A B C

重量：28 20 10

价值：28 20 10

根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决.

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。

程序员算法基础——贪心算法

贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。

比如一道常见的算法笔试题---- 跳一跳 ：

我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。

本文即是对这种贪心决策的介绍。

狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。 能用贪心解决的问题，也可以用动态规划解决。

而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：

我们发现的题目的核心在于 向右能到达的最远距离 ，我们用maxRight来表示；

此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。

贪心的思考过程类似动态规划，依旧是两步： 大事化小 ， 小事化了 。

大事化小：

一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；

小事化了：

从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的 向右能到达的最远距离 ；

在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。

如果是动态规划：

要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数；

有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;

容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；

根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不对？ 平时我们找零钱有这么复杂吗？

从贪心算法角度出发，当m10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。

从日常生活的经验知道，这么做是正确的，但是为什么？

假如我们把题目变成这样，原来的策略还能生效吗？

接下来我们来分析这种策略：

已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；

假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（zc），且纸币张数更少（x+y+za+b+c），即是用更少5元纸币得到最优解。

我们令k=5*(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币；（因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张）

容易知道，减少(c-z)张5元纸币，需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。

由此我们知道不可能存在使用更少5元纸币的更优解。

所以优先使用大额纸币是一种正确的贪心选择。

对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4；（1+1+1+7）

但如果只使用5元纸币，则张数是2；（5+5）

在这种情况下，优先使用大额纸币是不正确的贪心选择。（但用动态规划仍能得到最优解）

如果是动态规划：

前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。

我们用 dp[i]表示前i秒能完成的任务数 ；

在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：

1、不执行这个任务，那么dp[i]没有变化；

2、执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；

比如说对于任务j如果是第5秒开始第10秒结束，如果i=10，那么有 dp[i]=max(dp[i], dp[5] + 1)； （相当于把第5秒到第i秒的时间分配给任务j）

再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情？我换一种描述方式：

我们自然而然会想到一个策略： 先把结束时间早的兼职给做了！

为什么？

因为先做完这个结束时间早的，能留出更多的时间做其他兼职。

我们天生具备了这种优化决策的能力。

这是一道 LeetCode题目 。

这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。

因为（前i个人的最少糖果数）这种状态表示会收到第i+1个人的影响，如果a[i]a[i+1]，那么第i个人应该比第i+1个人多。

即是 这种状态表示不具备无后效性。

如果是我们分配糖果，我们应该怎么分配？

答案是： 从分数最低的开始。

按照分数排序，从最低开始分，每次判断是否比左右的分数高。

假设每个人分c[i]个糖果，那么对于第i个人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高）

但是，这样解决的时间复杂度为 O(NLogN) ，主要瓶颈是在排序。

如果提交，会得到 Time Limit Exceeded 的提示。

我们需要对贪心的策略进行优化：

我们把左右两种情况分开看。

如果只考虑比左边的人分数高时，容易得到策略：

从左到右遍历，如果a[i]a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。

再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：

如果a[i]a[i+1], 则有c[i]=c[i+1]+1；否则c[i]不变；

这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是 O(N) 。

题目给出关键信息：1、两个人过河，耗时为较长的时间；

还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去；

要保证总时间尽可能小，这里有两个关键原则： 应该使得两个人时间差尽可能小（减少浪费），同时船回去的时间也尽可能小（减少等待）。

先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配？

答案： 每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。

再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时ABC。

那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）

如果有A/B/C/D四个人，且耗时ABCD，这时有两种方案：

1、最快的来回送人方式，A+B去；A回；A+C去，A回；A+D去； 总耗时是B+C+D+2A （减少等待原则）

2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；总耗时是 3B+D+A （减少浪费原则）

对比方案1、2的选择，我们发现差别仅在A+C和2B；

为何方案1、2差别里没有D？

因为D最终一定要过河，且耗时一定为D。

如果有A/B/C/D/E 5个人，且耗时ABCDE，这时如何抉择？

仍是从最慢的E看。（参考我们无限多船的情况）

方案1，减少等待；先送E过去，然后接着考虑四个人的情况；

方案2，减少浪费；先送E/D过去，然后接着考虑A/B/C三个人的情况；（4人的时候的方案2）

到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。

根据5个人的情况，我们可以推出状态转移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);

再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：

dp[1] = a[1];

dp[2] = a[2];

dp[3] = a[2]+a[1]+a[3];

dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。

贪心的学习过程，就是对自己的思考进行优化。

是把握已有信息，进行最优化决策。

这里还有一些收集的 贪心练习题 ，可以实践练习。

这里 还有在线分享，欢迎报名。

贪心算法

在某一个标准下，优先考虑做满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。

即，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

局部最优 -?- 整体最优

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面是一个个具体 的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。 返回这个最多的宣讲场次。

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金 条，不管切成长度多大的两半，都要花费20个铜板。

一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。 金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20， 花费30；一共花费90铜板。

输入一个数组，返回分割的最小代价。

输入：

正数数组costs

正数数组profits

正数k

正数m

含义： costs[i]表示i号项目的花费

profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)

k表示你只能串行的最多做k个项目

m表示你初始的资金

说明：

你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。

输出： 你最后获得的最大钱数。