贪心算法详解贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

如单源最短路经问题，最小生成树问题等。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本要素：1.贪心选择性质。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当达到算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：从问题的某一初始解出发；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种贪心策略，都是无法成立（无法被证明）的，解释如下：贪心策略：选取价值最大者。

反例：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，则答案错误。

但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决.所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。

（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。

下面我们看一些简单例题。

例24：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。

分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。

因此，我们设计出如下算法:读入N, M,矩阵数据；Total := 0;For I := 1 to N do begin {对N行进行选择}选择第I行最大的数,记为K；Total := Total + K；End；输出最大总和Total；从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。

但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。

特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。

对于能否使用贪心策略，应从理论上予以证明。

下面我们看看另一个问题。

例25：部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。

已知第i种食品的最多拥有W i公斤，其商品价值为V i元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。

因此我们非常容易设计出如下算法：问题初始化；{读入数据}按V i从大到小将商品排序；I := 1;repeatif M = 0 then Break; {如果卡车满载则跳出循环}M := M - W i;if M >= 0 then 将第I种商品全部装入卡车else将(M + W i)重量的物品I装入卡车;I := I + 1; {选择下一种商品}until (M <= 0) OR (I >= N)在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(V i)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。

Program Exam25;Const Finp='Input.Txt';Fout='Output.Txt';Var N,M :Longint;S :Real;P,W :Array[1..100] Of Integer; Procedure Init; {输出}Var I :Integer;BeginAssign(Input,Finp); Reset(Input);Readln(M,N);For I:=1 To N Do Readln(W[I],P[I]);Close(Input);End;Procedure Sort(L,R:Integer); {按收益值从大到小排序}Var I,J,Y :Integer;X :Real;BeginI:=L; J:=R;X:=P[(L+R) Div 2]/W[(L+R) Div 2];RepeatWhile (I<R)And(P[I]/W[I]>=X) Do Inc(I);While (P[J]/W[J]<=X)And(J>L) Do Dec(J);If I<=J ThenBeginY:=P[I]; P[I]:=P[J]; P[J]:=Y;Y:=W[I]; W[I]:=W[J]; W[J]:=Y;Inc(I); Dec(J);End;Until I>J;If I<R Then Sort(I,R);If L<J Then Sort(L,J);End;Procedure Work;Var I :Integer;BeginSort(1,N);For I:=1 To N DoIf M>=W[I] Then {如果全部可取，则全取}BeginS:=S+P[I]; M:=M-W[I];EndElse {否则取一部分}BeginS:=S+M*(P[I]/W[I]); Break;End;End;Procedure Out; {输出}BeginAssign(Output,Fout); Rewrite(Output);Writeln(S:0:0);Close(Output);End;Begin {主程序}Init;Work;Out;End.因此，利用贪心策略解题，需要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：①可通过局部的贪心选择来达到问题的全局最优解。

运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。

在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。

②原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。

在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。

其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。

在得出贪心标准之后应给予严格的数学证明。

下面来看看0-1背包问题。

给定一个最大载重量为M的卡车和N种动物。

已知第i种动物的重量为W i，其最大价值为V i，设定M，W i，V i均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。

分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。

即确定一组X1，X2，…，Xn， Xi∈{0,1}f(x)=max(∑X i*V i) 其中，∑(X i*W i)≦W从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。

也就是可以按价值质量比（V i/W i）的大小来进行选择。

可以看出，每做一次选择，都是从剩下的动物中选择那些V i/W i最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。

情况A：按照上述思路，三种动物的V i/W i分别为2,2,2.14。

显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。

情况B：不按上述约束条件，直接选择A和B。

可以得到价值80+100=180，卡车装载的重量为40+50=90。

没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。