贪心算法几个经典例子详细解读

① 哈夫曼编码（贪心算法）

参考： 哈夫曼编码

哈夫曼编码是一种十分有效的编码方法，广泛应用于 数据压缩 中
通过采用 不等长 的编码方式，根据 字符频率的不同 ，选择 不同长度的编码 ，对频率 越高 的字符采用 越短 的编码实现数据的高度压缩。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。

下面看一个例子：
假如我们有一个包含1000个字符的文件，每个字符占1个byte(1byte=8bits)，则存储这100个字符一共需要8000bits。这还是有一些大的
那我们统计一下这1000个字符中总共有多少种字符，原来需要8bit来表示一个字符，如果使用更少的位数来表示这些字符，则可以减少存储空间。
假设这1000个字符中总共有a、b、c、d、e、f共6种字符，使用使用3个二进制位来表示的话，存储这1000个字符就只需要3000bits，比原来更节省存储空间。

或许还可以再压缩一下：
根据字符出现的 频率 给与字符 不等长 的编码，频率越高的字符编码越短，频率越低的字符编码越长。
它不能像等长编码一样直接按固定长度去读取二进制位，翻译成字符，为了能够准确读取翻译字符，它要求一个字符的编码不能是另外一个字符的前缀。

假设a、b、c、d、e、f这6个字符出现的频率依次降低，则我们可以给与他们这样的编码

假如字符的出现频率如图所示，按照这样的编码表示的话，总位数如图，一共2100bits，更加节省空间了

贪心策略：频率小的字符，优先入队。

步骤：
1.将每一个字符作为节点，以出现频率大小作为权重，将其都放入 优先队列 中（一个最小堆）；
2.每次出队两个节点并创建一个父节点，使其权值为刚刚出队的节点的权值和，并且为两个节点的父节点（合并）。然后将这个树入队。
3.重复操作2，直到队列中只有一个元素（此时这个元素表示形式应该为一个树）时，完成创建。

创建好了树，该怎么编码呢？
我们对一个哈夫曼树，从父节点开始的所有节点，往左边标0，右边标1。那么到达叶子节点的顺次编码就可以找到了。

C：字符集合
Q：优先队列
EXTRACT-MIN：传入一个队列，出队最小的元素
INSERT：将z插入到Q中

当for循环结束之后，此时队列中只有一个元素，就是我们需要的哈夫曼树，最后返回此树即可。

假设T树已经是一个最优的树，假设x、y的频率小于等于最低处的a、b，然后交换x、a，y、b。

计算代价是否发生变化。
比如这里比较 T 变成 T ’ 后代价是否变化，发现代价变小或不变。

同理T’到T’’，又因为T本来假设就是最优的，所以只能相等
所以T’’也应该符合条件，即贪婪算法，每次取最小的两个节点出来这种做法是正确的

② 贪心算法及其应用

求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。

比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装100KG重量的袋子，怎么装才能使得袋子中的豆子价值最大？

我们首先看看这个问题是否符合贪心算法的使用场景？限制值是袋子100KG，期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法，每一个步骤都寻找当下的最优解，怎么做呢？

把仓库里面的每种豆子价值除以重量，得出每种豆子的单价，那么当下的最优解，肯定是尽可能最多地装单价最贵的，也就是先把20KG的黄豆都装上，然后再把30KG的绿豆都装上，再装50KG的红豆，那么此时正好装满袋子，总价值将是270元，这就是通过贪心算法求解的答案。

贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证，我们不用那样，只要心里举几个例子，验证下是否比它更好即可，如果举不出例子，那么就可以认为这就是最优解了。

虽然贪心算法虽然在大部分实践场景中都能得到最优解，但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径，那么答案肯定就是S->A->E->T，总代价为1+4+4=9；

然而，实际上的最短路径是S->B->D->T，总代价为6。

所以，不能所有这类问题都迷信贪心算法的求解，但其作为一种算法指导思想，还是很值得学习的。

除了以上袋子装豆子的问题之外，还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题，即找到问题的限制值和期望值。

我们有m个糖果要分给n个孩子，n大于m，注定有的孩子不能分到糖果。其中，每个糖果的大小都不同，分别为S1,S2,S3...,Sm，每个孩子对糖果的需求也是不同的，为N1,N2,N3...,Nn，那么我们如何分糖果，才能尽可能满足最多数量孩子的需求？

这个问题中，限制值是糖果的数量m，期望值满足最多的孩子需求。对于每个孩子，能用小的糖果满足其需求，就不要用大的，避免浪费。所以我们可以给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。

我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张，现在要购买一个价值K元的东西，请问怎么才能适用最少的纸币？

这个问题应该不难，限制值是各个纸币的张数，期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱，当再加一张100元就超过K时，就更换小面额的，直至正好为K元。

对于n个区间[L1,R1],[L2,R2]...[Ln,Rn]，我们怎么从中选出尽可能多的区间，使它们不相交？

我们需要把这个问题转换为符合贪心算法特点的问题，假设这么多区间的最左端点是Lmin，最右端点是Rmax，那么问题就是在[Lmin,Rmax]中，选择尽可能多的区间往里面塞，并且保证它们不相交。这里，限制值就是区间[Lmin,Rmax]，期望值就是尽可能多的区间。

我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。

贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。

③ 贪心算法的例题分析

例题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就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

④ 贪心算法

在某一个标准下，优先考虑做满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。
即，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优 -?-> 整体最优

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

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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表示你初始的资金
说明：
你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出： 你最后获得的最大钱数。

⑤ 求一个算法(贪心算法)

首先,无所谓哪里密集哪里不密集的说法,这是人为的区分,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了.
既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走，思想如下:
判断当前格子右、下两个相邻的格子是否有金块，情形如下：
1）如果一个有一个没有，则往有金块的格子走
2）如果都没有或都有，则需要判断往哪个方向走能更快的拾到下一个金块，方法如下：
让机器人假设地各往两个方向走一步，然后对当前格子作判断情形如下：
A)一个格子继续走能拾到金块，另一个不能，则上一步往该格子走
B)如果仍旧都有或都没有，重复2）直到找到符合A）的情形。

假设棋盘是N*N个格子，则贪心算法最坏的情形是要遍历整个棋盘，比如只有第一个格子有金块时，就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4*N个格子。
时间复杂度上来算的话，应该是O（nLogn）