贪心法
课题：贪心法 目标：
知识目标：贪心的原理递与贪心的实现 能力目标：贪心的原理
重点：贪心算法的应用 难点：贪心的理解 板书示意：
1） 贪心的引入（例24）
2） 贪心的应用（例25、例26、例27、例28）
授课过程：
若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。
下面我们看一些简单例题。
例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元/公斤，编程确定一个装货方案，使得装入卡车中的
1
所有物品总价值最大。
分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
因此我们非常容易设计出如下算法：
问题初始化； {读入数据} 按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
2
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; 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 {否则取一部分} Begin S:=S+M*(P[I]/W[I]); Break; End; End; Procedure Out; {输出} Begin Assign(Output,Fout); Rewrite(Output); Writeln(S:0:0); Close(Output); End; Begin {主程序} Init; Work; Out; End. 因此，利用贪心策略解题，需要解决两个问题： 首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点： ① 可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。 ② 原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩 3 下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。 其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。 下面来看看0-1背包问题。 给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。 分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。 即确定一组X1，X2，…，Xn， Xi∈{0,1} f(x)=max(∑Xi*Vi) 其中，∑(Xi*Wi)≦W 从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（Vi/Wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子： 设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 卡车装载货物情况分析 从图23中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。 因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。 例26排队打水问题 有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不 4 相等，应如何安排他们的打水顺序才能使他们花费的时间最少？ 分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤： (1) 将输入的时间按从小到大排序； (2) 将排序后的时间按顺序依次放入每个水龙头的队列中； (3) 统计，输出答案。 参考程序： Program Exam26; Const Finp='Input.Txt'; Fout='Output.Txt'; Var A :Array[1..100] Of Integer; S :Array[1..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(A[I]); Close(Input); End; Procedure Sort(L,R:Integer); {将时间从小到大排序} Var I,J,X,Y :Integer; Begin I:=L; J:=R; X:=A[(L+R) Div 2]; Repeat While (A[I]<=X)And(I Y:=A[I]; A[I]:=A[J]; A[J]:=Y; Inc(I); Dec(J); End; Until I>J; If L Procedure Work; Var I,J,K :Integer; Begin Fillchar(S,Sizeof(S),0); J:=0; Min:=0; For I:=1 To N Do {用贪心法求解} 5
高中信息技术 全国青少年奥林匹克联赛教案 贪心法二
