第五讲--贪心算法PPT课件.ppt

第五讲贪心算法;;一、引入：;分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:

读入N,M,矩阵数据；

Total:=0;

ForI:=1toNdobegin {对N行进行选择}

选择第I行最大的数,记为K；

Total:=Total+K；

End；

输出最大总和Total；;从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。

特别注意的是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。;二、应用举例;分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。;问题初始化； {读入数据}

按Pi/Wi从大到小将商品排序；

I:=1;

repeat

ifM=0thenBreak; {如果卡车满载则跳出循环}

M:=M-Wi;

ifM=0then将第I种商品全部装入卡车

else

将(M+Wi)重量的物品I装入卡车;

I:=I+1; {选择下一种商品}

until(M=0)OR(I=N)

在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Pi/Wi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。;ProgramExam1;

ConstFinp=Input.Txt;

Fout=Output.Txt;

VarN,M:Longint;

S:Real;

P,W:Array[1..100]OfInteger;

ProcedureInit;{输出}

VarI:Integer;

Begin

Assign(Input,Finp);Reset(Input);

Readln(M,N);

ForI:=1ToNDoReadln(W[I],P[I]);

Close(Input);

End;;ProcedureSort(L,R:Integer);{按收益值从大到小排序}

VarI,J,Y:Integer;

X:Real;

Begin

I:=L;J:=R;

X:=P[(L+R)Div2]/W[(L+R)Div2];

Repeat

While(IR)And(P[I]/W[I]=X)DoInc(I);

While(P[J]/W[J]=X)And(JL)DoDec(J);

IfI=JThen

Begin

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;

UntilIJ;

IfIRThenSort(I,R);

IfLJThenSort(L,J);

End;;ProcedureWork;

VarI:Integer;

Begin

Sort(1,N);S:=0;

ForI:=1ToNDo

IfM=W[I]Then{如果全部可取，则全取}

Begin

S:=S+P[I];M:=M-W[I];

End

Else{否则取一部分}

Begin

S:=S+M*(P[I]/W[I]);Break;

End;

End;;ProcedureOut;{输出}

Begin

Assign(Output,Fout);Rewrite(Output);

Writeln(S:0:0);

Close(Output);

End;

Begin{主程序}

Init;

Work;

Out;

End.

;因此，利用贪心策略解题，需要解决两个问题：

首先，确定