贪心算法几个题目

❶ 贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

❷ 贪心算法之会场安排问题

三星算法之间最好还是不要安排互相的问题，这样不利于你们俩的关系的便有好。

❸ 贪心算法(硬币找零问题)

小Q手上有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出 1 到 m 之间的任意值。输入的第一行为两个整数： m 和 n ，他们的意义如题目描述。 接下来的 n 行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值。输出的最少需要携带的硬币数量，如果无解则输出 -1 。
50% 的数据： 1<=n<=10 ， 1<=m<=10^3 ；
100% 的数据： 1<=n<=100 ， 1<=m<=10^9 ；

数据量很大，dp不好做，也不好压缩，应该采用贪心的思路。首先如果没有面值为 1 的硬币必定无法满足要求可以直接输出 -1 ，接下来考虑贪心策略，设想如果能够组合出 1 到 5 之间的任何数值，只要一个 6 的硬币就能组合出 1 到 11 的任意值，既如果当前能够组合出 1 到 n 的硬币，再加入一个 n+1 面值的银币就能组合出 1 到 n+n+1 的所有面值。所以基本思路就是用一个变量 cur 存储当前能表示的面值，将硬币排序，从大往小找到第一个小于等于 cur+1 的硬币，硬币数加一同时更新 cur ，当 cur 大于 m 时输出。

❹ 计算题【用贪心算法求解付款问题】

不是
贪心得到的结果是 3元，1元，5角，1角

最优是一张三元，两张八角。

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

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

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

我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。
本文即是对这种贪心决策的介绍。

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

而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：
我们发现的题目的核心在于 向右能到达的最远距离 ，我们用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]的所有值。

似乎有些不对？ 平时我们找零钱有这么复杂吗？
从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。
从日常生活的经验知道，这么做是正确的，但是为什么？

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

接下来我们来分析这种策略：
已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；
假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（z<c），且纸币张数更少（x+y+z<a+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三个人，并且耗时A<B<C。
那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）

如果有A/B/C/D四个人，且耗时A<B<C<D，这时有两种方案：
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个人，且耗时A<B<C<D<E，这时如何抉择？
仍是从最慢的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]的值。

贪心的学习过程，就是对自己的思考进行优化。
是把握已有信息，进行最优化决策。
这里还有一些收集的 贪心练习题 ，可以实践练习。
这里 还有在线分享，欢迎报名。

❻ 贪心算法几个经典例子

[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于本例题中的3种贪心策略，都无法成立，即无法被证明。

❼ 求贪心算法题（Pascal）

《编程之美》里面有一道买书问题的贪心算法。
题目是这样的：
在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。上柜的《哈利波特》平装本系列中，一共有五卷。假设每一卷单独销售均需8欧元 。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中，根据购买的卷数及本数，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望计算出的总额尽可能的低。
要求根据以上需求，设计出算法，能够计算出读者所购买一批书的最低价格。

❽ 关于编程的贪心法

定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是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）每次选取单位重量价值最大的物品，成为解本题的策略。 值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。 贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。 可惜的是，它需要证明后才能真正运用到题目的算法中。 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： （1）贪心策略：选取价值最大者。 反例： 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，则答案错误。 【注意：如果物品可以分割为任意大小，那么策略3可得最优解】 对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。 但是，如果题目是如下所示，这个策略就也不行了。 W=40 物品：A B C 重量：28 20 15 价值：28 20 15 附：本题是个NP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
[编辑本段]备注
贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。 所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）
[编辑本段]附贪心算法成功案例之一
马踏棋盘的贪心算法 123041-23 XX 【问题描述】 马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。 【初步设计】 首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下： 1、 输入初始位置坐标x,y； 2、 步骤 c: 如果c> 64输出一个解，返回上一步骤c-- (x,y) ← c 计算(x,y)的八个方位的子结点，选出那此可行的子结点 循环遍历所有可行子结点，步骤c++重复2 显然（2）是一个递归调用的过程，大致如下： void dfs(int x,int y,int count) { int i,tx,ty; if(count> N*N) { output_solution();//输入一个解 return; }

❾ 算法09-贪心算法

贪心算法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

很多情况下，可以在某一步用贪心算法，全局再加一个搜索或递归或动态规划之类

贪心法可以解决一些最优化问题，如:求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
一单一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

当硬币可选集合固定:Coins = [20,10,5,1],求最少几个硬币可以拼出总数。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面这些硬币依次是后面硬币的整数倍，可以用贪心法，能得到最优解，

贪心法的反例
非整除关系的硬币，可选集合:Coins = [10,9,1],求拼出总数为18最少需要几个硬币？
最优化算法:9 + 9 = 18 两个9
贪心算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八个1

简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的最终方案都作出选择，不能回退。
动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
因为当移动下标指向nums.size - 2时：
如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
-2 ：向左转 90 度
-1 ：向右转 90 度
1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）
注意：
北表示 +Y 方向。
东表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：[5,5,10]
输出：true
示例 3：
输入：[10,10]
输出：false
示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2

❿ 收集各类贪心算法（C语言编程）经典题目

举个例子,假如你买东西，老板需要找给你99分钱，他有上面面值分别为25分，10分，5分，1分的硬币（都是假如，不符合实际），他得找你3个25分，2个10分的，4个1分的才为最佳方案！
用贪心算法编写程序实现！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}