高中信息技术 全国青少年奥林匹克联赛教案 贪心法二VIP免费

贪心法课题：贪心法目标：知识目标：贪心的原理递与贪心的实现能力目标：贪心的原理重点：贪心算法的应用难点：贪心的理解板书示意：1）贪心的引入（例24）2）贪心的应用（例25、例26、例27、例28）授课过程：若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。下面我们看一些简单例题。例24：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:读入N,M,矩阵数据；Total:=0;ForI:=1toNdobegin{对N行进行选择}选择第I行最大的数,记为K；Total:=Total+K；End；输出最大总和Total；从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。例25：部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。因此我们非常容易设计出如下算法：问题初始化；{读入数据}按Vi从大到小将商品排序；I:=1;repeatifM=0thenBreak;{如果卡车满载则跳出循环}M:=M-Wi;ifM>=0then将第I种商品全部装入卡车else将(M+Wi)重量的物品I装入卡车;I:=I+1;{选择下一种商品}until(M<=0)OR(I>=N)在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。ProgramExam25;ConstFinp='Input.Txt';Fout='Output.Txt';VarN,M:Longint;S:Real;P,W:Array[1..100]OfInteger;ProcedureInit;{输出}VarI:Integer;BeginAssign(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;BeginI:=L;J:=R;X:=P[(L+R)Div2]/W[(L+R)Div2];RepeatWhile(I=X)DoInc(I);While(P[J]/W[J]<=X)And(J>L)DoDec(J);IfI<=JThenBeginY:=P[I];P[I]:=P[J];P[J]:=Y;Y:=W[I];W[I]:=W[J];W[J]:=Y;Inc(I);Dec(J);End;UntilI>J;IfI=W[I]Then{如果全部可取，则全取}BeginS:=S+P[I];M:=M-W[I];EndElse{否则取一部分}BeginS:=S+M*(P[I]/W[I]);Break;End;End;ProcedureOut;{输出}BeginAssign(Output,Fout);Rewrite(Output);Writeln(S:0:0);Close(Output);End;Begin{主程序}Init;Work;Out;End.因此，利用贪心策略解题，需要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：①可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。②原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优...