贪心算法详解分析.docx

1、贪心算法详解分析贪心算法详解贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法的基本要素：1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的

2、主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1. 不能保证求得的

3、最后解是最佳的；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

4、= 0 then 将第I种商品全部装入卡车 else 将(M + Wi)重量的物品I装入卡车; I := I + 1; 选择下一种商品until (M = N)在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。Program Exam25;Const Finp=Input.Txt; Fout=Output.Txt;Var N,M :Longint; S :Real; P,W :Array1.100 Of Integer;Procedure Init; 输出Var I :Integer;Begin Assign(In

5、put,Finp); Reset(Input); Readln(M,N); For I:=1 To N Do Readln(WI,PI); 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=X) Do Inc(I); While (PJ/WJL) Do Dec(J); If IJ; If IR Then Sort(I,R); If L=WI Then

6、如果全部可取，则全取 Begin S:=S+PI; M:=M-WI; End Else 否则取一部分 Begin S:=S+M*(PI/WI); Break; End;End;Procedure Out; 输出Begin Assign(Output,Fout); Rewrite(Output); Writeln(S:0:0); Close(Output);End;Begin 主程序 Init; Work; Out;End.因此，利用贪心策略解题，需要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：1可通过局部的贪心选择来达到问题的全局最优解。运

7、用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。2原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数

8、学证明。下面来看看0-1背包问题。给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。即确定一组X1，X2，Xn， Xi0,1f(x)=max(Xi*Vi) 其中，(Xi*Wi)W从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（Vi/Wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这

9、种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。情况A：按照上述思路，三种动物的Vi/Wi分别为2,2,2.14。显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。情况B：不按上述约束条件，直接选择A和B。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。问题出现在什么地方呢？我们看看图2-18从图23

10、中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。 例26排队打水问题有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：(1)将输入的时间按从小到大排序；(2)将排序后的时间按顺序依

11、次放入每个水龙头的队列中； (3)统计，输出答案。参考程序：Program Exam26;Const Finp=Input.Txt; Fout=Output.Txt;Var A :Array1.100 Of Integer; S :Array1.100 Of Longint; N,M :Integer; Min :Longint;Procedure Init; 读入数据Var I :Integer;Begin Assign(Input,Finp); Reset(Input); Readln(N,M); For I:=1 To N Do Read(AI); Close(Input);End;Pr

12、ocedure Sort(L,R:Integer); 将时间从小到大排序Var I,J,X,Y :Integer;Begin I:=L; J:=R; X:=A(L+R) Div 2; Repeat While (AI=X)And(I=X)And(JL) Do Dec(J); If IJ; If LI Then Sort(I,R);End;Procedure Work;Var I,J,K :Integer;Begin Fillchar(S,Sizeof(S),0); J:=0; Min:=0; For I:=1 To N Do 用贪心法求解 Begin Inc(J); If J=M+1 Then

13、 J:=1; SJ:=SJ+AI; Min:=Min+SJ; End; Assign(Output,Fout); Rewrite(Output); 输出解答 Writeln(Min); Close(Output);End;Begin 主程序 Init; Sort(1,N); Work;End.均分纸牌有 N 堆纸牌，编号分别为 1，2，, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的

14、堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： 9 8 17 6移动3次可达到目的：从 取 4 张牌放到 （9 8 13 10） - 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10）。输入格式N（N 堆纸牌，1 = N = 100）A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000输出格式 Output Format所有堆均达到相等时的最少移动次数。样例输入49 8 17 6样例输出3题解：program zzh;vara:array1.99of integer;b

15、,c,d,e,f,g,n,i:integer;beginread(n);c:=0;for b:=1 to n doread(ab);for b:=1 to n doc:=c+ab;d:=c div n;if c mod n=0 thenbeginfor e:=1 to n-1 doif daethenbeginae+1:=ae+1+ae-d;ae:=d;f:=f+1;end;write(f);end;end.金银岛描述某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛

16、上金属有s个种类, 每种金属重量不同，分别为n1, n2, . , ns，同时每个种类的金属总的价值也不同，分别为v1,v2, ., vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。输入第1行是测试数据的组数k，后面跟着k组输入。每组测试数据占3行，第1行是一个正整数w (1 = w = 10000)，表示口袋承重上限。第2行是一个正整数s (1 = s =100)，表示金属种类。第3行有2s个正整数，分别为n1, v1, n2, v2, . , ns, vs分别为第一种，第二种，.，第s种金属的总重量和总价值

17、(1 = ni= 10000, 1 = vi= 10000)。输出k行，每行输出对应一个输入。输出应精确到小数点后2位。样例输入250410 100 50 30 7 34 87 1001000051 43 43 323 35 45 43 54 87 43样例输出171.93508.00贪心题目，先算出每种金属单价d， 按照d进行排序， 然后贪心地拣前面几个，直到背包满。vara,b:array0.100 of longint;p:array0.100 of real;n,i,j,k,s,m,g:longint;tot:real;procedure sort(l,r: longint);vari

18、,j,y:longint;x,tt:real;begini:=l;j:=r;x:=p(l+r) div 2;repeat while pix do inc(i); while xj) then begin tt:=pi; pi:=pj; pj:=tt; y:=ai; ai:=aj; aj:=y; y:=bi; bi:=bj; bj:=y; inc(i); j:=j-1; end;until ij;if lj then sort(l,j);if i0)and(m0) do if m=ai then begin dec(m,ai); tot:=tot+bi; dec(i); end else be

19、gin tot:=tot+m*pi; m:=0; end; writeln(tot:0:2); end;end.装箱问题查看提交统计提问总时间限制:1000ms内存限制:65536kB描述一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。输入输入文件包括几行，每一行代表一个订单。每个

20、订单里的一行包括六个整数，中间用空格隔开，分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。输出除了输入的最后一行6个0以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。样例输入0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 样例输出2 1 解题思路这个问题描述得比较清楚，在这里只解释一下输入输出样例：共两组有效输入，第一组表示有4个3X3的产品和1个6X6的产品，此时4个3X3的产品占用一个箱子，另外1个6X6的产品占用一个箱子，所以箱子数是2；第二组表示有7个1X1的产品，5个2X2的产品和1个3X3

21、的产品，可以把它们统统放在一个箱子中，所以输出是1。分析6个型号的产品占用箱子的具体情况如下：6X6的产品每个会占用一个完整的箱子，并且没有空余的空间；5X5的产品每个占用一个新的箱子，并且留下11个可以盛放1X1的产品的空余空间；4X4的产品每个占用一个新箱子，并且留下5个可以盛放2X2的产品的空余空间；3X3的产品比较复杂，首先3X3的产品不能放在原来盛放5X5或者4X4的箱子中，那么必须为3X3的产品另开新的箱子，新开的箱子数目等于3X3的产品的数目除以4向上取整；同时需要讨论为3X3的产品新开箱子时，剩余的空间可以盛放多少2X2和1X1的产品(这里如果空间可以盛放2X2的产品，就将它记

22、入2X2的空余空间，等到2X2的产品全部装完，如果还有2X2的空间剩余，再将它们转换成1X1的剩余空间)。分情况讨论为3X3的产品打开的新箱子额中剩余的空位，共为4种情况：第一种，3X3的产品的数目正好是4的倍数，所以没有空余空间；第2种，3X3的产品数目是4的倍数加1，这时还剩5个2X2的空位和7个1X1的空位；第3种，3X3的产品数目是4的倍数加2，这时还剩3个2X2的空位和6个1X1的空位；第4种，3X3的产品的数目是4的倍数加3，这时还剩1个2X2的空位和5个1X1的空位；处理完3X3的产品，就可以比较一下剩余的2X2的空位和2X2产品的数目，如果产品数目多，就将2x2的空位全部填满，

23、再为2x2的产品打开新箱子，同时计算新箱子中1x1的空位，如果剩余空位多，就将2x2的产品全部填入2x2的空位，再将剩余的2x2空位转换成1x1的空位；最后处理1x1的产品，比较一下1x1的空位与1x1的产品数目，如果空位多，将1x1的产品全部填入空位，否则，先将1x1的空位填满，然后再为1x1的产品打开新的箱子。var i,tt,ans,j:longint;a:array0.6of longint;f:array1.6,1.6,0.36of longint;begin for i:=1 to 6 do read(ai); f3,2,7:=1; f3,2,6:=1; f3,2,5:=1; while a1