贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量攻欢什。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的走配分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可称以通过一系列局部最优的选择即贪婪选择来今哥读绿支修科亲模空策达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子预了川问题。每做一次贪婪选择就将所求问题简化为一个规模精含根精更小的子问题，最终可得到问题的一个整体最优解。
贪婪算法可解决的问题通常大部分都有如下的特性:
⑴有一个以最优方式年飞接基客英来解决的问题。为了构造布建采劳转久统问题的解决方案，有一个候选的对象的集合:比如不同面值的硬币。
⑵随着算法的进行，将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
⑶有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
⑷还有一个函数检要树逐信门针则或念州罪查是否一个候选对象的集合是引可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方早法的最优性。
⑸选择函数可以指此迫给料变后或作岁过出哪一个剩余的候选对象最有希望构成问题的解。
⑹最后，目标函数给出解的值。
为了解决问转式从题，需要寻找一个构成解的候选对象集合，它可以优化目标过夫专衡但函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢终将势弃并不再考虑;否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
⒈建立数学模型来描述问题。
⒉把求解的问题分成若干个子问题。
⒊对每一子问题求解，得到子问题的局部最优解。
⒋把子问题的解局部最优解合成原来解问题的一个解。
从问题的某一初始解出发;
while能朝给定总目标前进一步do
求出可行解的一个解元素括土势刻热究连正去首力;
下面是一个可以试用贪心算法解的题目，贪心解的确不错副联济思断型染消赵远继，可惜不是最优解。
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
放交娘点厚毫进要求尽可能让装入背包中真粮术初直齐杆的物品总价值最大，但不能超过总容量。
物品ABCDEFG
重量35306050401兰算职厚的伤025
价值10403050354030
分析:
目标函数:∑pi最大
约束条件是装入的关田善物品总重量不超过背包容量:∑wi<=M(M=150)
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优
⑵每次挑选所占重量最小的物品装入是否能得到最优解
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪缩心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造害甲弱展交尔队贪心策略不是很困难。
南冲调独础阻甲离应可惜的是，它需要证明定小后才能真正运用到题目的算法中。
一般来说，贪心算法的则比均问绿往断证明围绕着:整个问题的最优解一定由在贪优晶值置稳道造查离似心策略中存在的子问题的最优解得世密交创来的。
对于例题中的3种贪心策略，都是无法成立(无法被证明)的，解释如下:
⑴贪心策略:选取价值最大者。
反例:
W=30
物品:ABC
加沿连极镇似永重量:281212
价值:302020
根据策略，首先选取物品A，接下厚跟结还请迅态款换来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略:选取单位重量价值最大的物品。
重量:282010
价值:282010
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
生理【注意:如果物品可以分割为任意大小，那么策略3可得最优解】
对于选本六每歌八永取单位重量价值最大的物品这个策略，可以再加一条优化的规则:对于单位重量价值一样的，则优先选择重量小的!这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
重量:252015
价值:影紧击征组或映演首端252015
附:本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了队新的解法。
贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式
马踏棋盘的贪心算法
123041-23XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。
【初步设计】
⒈输入初始位置坐标x,y;
⒉步骤c:
如果c>64输出一个解，返回上一步骤c--
(x,y)←c
计算(x,y)的八个方位的子结点，选出那此可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下:
#defineN8
……
voiddfs(intx,inty,intcount)
{
inti,tx,ty;
if(count>N*N)
output_solution();//输出一个解
return;
}
for(I=0;i<8;++i)
tx=hn.x;//hn[]保存八个方位子结点
ty=hn.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);
Var
Road:array[1..10,1..10]ofinteger;
x,y,x1,y1,total:integer;
ProcedureFind(x,y:integer);
varNx,Ny,i:integer;
Begin
Fori:=1to8dobegin{8个方向}
If(x+FXxin[1..8])and(y+FXyin[1..8])Then{确定新坐标是否越界}
IfRoad[x+Fxx,y+Fxy]=0Thenbegin{判断是否走过}
Nx:=x+FXx;Ny:=y+FXy;Road[Nx,Ny]:=1;{建立新坐标}
If(Nx=x1)and(Ny=y1)Theninc(total)
elseFind(Nx,Ny);{递归}
Road[Nx,Ny]:=0{回朔}
end
End;
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('Eorror'){判断是否越界}
ElseFind(x,y);
Writeln('Total:',total){打出总数}
END.
怎么才能快速地得到部分解呢
【贪心算法】
如把3/7和13/23分别化为三个单位分数的和
设a、b为互质正整数，a 步骤一:用b除以a，得商数q1及余数r1。(r1=b-a*q1) 步骤二:把a/b记作:a/b=1/(q1+1)+(a-r)/b(q1+1) 步骤三:重复步骤2，直到分解完毕 3/7=1/3+2/21=1/3+1/11+1/231 13/23=1/2+3/46=1/2+1/16+1/368 设某个真分数的分子为a，分母为b; 把b除以a的商部分加1后的值作为埃及分数的某一个分母c; 将a乘以c再减去b，作为新的a; 将b乘以c，得到新的b; 如果a大于1且能整除b，则最后一个分母为b/a;算法结束; 或者，如果a等于1，则，最后一个分母为b;算法结束; 否则重复上面的步骤。 备注:事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。