发布时间 : 星期五 文章贪心算法详解更新完毕开始阅读8e53bfca5a8102d277a22f2b
贪心算法详解
贪心算法思想：
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素：
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 选择第I行最大的数,记为K； Total := Total + K； End； 输出最大总和Total； {对N行进行选择}
从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。
特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。
例25：部分背包问题
给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。
分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
因此我们非常容易设计出如下算法：
问题初始化； {读入数据} 按Vi从大到小将商品排序； I := 1; repeat if M = 0 then Break; {如果卡车满载则跳出循环} M := M - Wi; if M >= 0 then 将第I种商品全部装入卡车 else 将(M + Wi)重量的物品I装入卡车; I := I + 1; {选择下一种商品} until (M <= 0) OR (I >= N)
在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。
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; Begin
Assign(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; Begin
I:=L; J:=R;
X:=P[(L+R) Div 2]/W[(L+R) Div 2]; Repeat
While (I
Y:=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 Procedure Work; Var I :Integer; Begin Sort(1,N); For I:=1 To N Do If M>=W[I] Then {如果全部可取，则全取} Begin S:=S+P[I]; M:=M-W[I]; End Else {否则取一部分}