高中信息技术全国青少年奥林匹克联赛教案贪心法二.pdf
《高中信息技术全国青少年奥林匹克联赛教案贪心法二.pdf》由会员分享,可在线阅读,更多相关《高中信息技术全国青少年奥林匹克联赛教案贪心法二.pdf(14页珍藏版)》请在三一文库上搜索。
1、1 贪心法 课题:贪心法 目标: 知识目标:贪心的原理递与贪心的实现 能力目标:贪心的原理 重点:贪心算法的应用 难点:贪心的理解 板书示意: 1) 贪心的引入(例24) 2) 贪心的应用(例25、例 26、例 27、例 28) 授课过程: 若在求解一个问题时,能根据每次所得到的局部最优解,推导出全局最优或最优目标。 那么, 我们可以根据这个策略,每次得到局部最优解答,逐步而推导出问题,这种策略称为 贪心法。 下面我们看一些简单例题。 例 24:在 N 行 M列的正整数矩阵中,要求从每行中选出1 个数,使得选出的总共N个 数的和最大。 分析:要使总和最大,则每个数要尽可能大,自然应该选每行中最
2、大的那个数。因此, 我们设计出如下算法: 读入 N, M, 矩阵数据; Total := 0; For I := 1 to N do begin 对 N行进行选择 选择第 I 行最大的数 , 记为 K; Total := Total + K; End ; 输出最大总和 Total ; 从上例中我们可以看出,和递推法相仿, 贪心法也是从问题的某一个初始解出发,向给 定的目标递推。 但不同的是, 推进的每一步不是依据某一固定的递推式,而是做一个局部的 最优选择,即贪心选择(在例中,这种贪心选择表现为选择一行中的最大整数),这样,不 断的将问题归纳为若干相似的子问题,最终产生出一个全局最优解。 特别
3、注意的是是,局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所 在。对于能否使用贪心策略,应从理论上予以证明。下面我们看看另一个问题。 例 25:部分背包问题 给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第i 种食品 的最多拥有Wi公斤,其商品价值为Vi元/ 公斤,编程确定一个装货方案,使得装入卡车中的 2 所有物品总价值最大。 分析: 因为每一个物品都可以分割成单位块,单位块的利益越大显然总收益越大,所以 它局部最优满足全局最优,可以用贪心法解答,方法如下: 先将单位块收益按从大到小进行 排列,然后用循环从单位块收益最大的取起,直到不能取为止便得到了最优解。 因
4、此我们非常容易设计出如下算法: 问题初始化;读入数据 按 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 = N) 在解决上述问题的过程中,首先根据题设条件,找到了贪心选择标准(Vi) ,并依据这个 标准直接逐步去求最优解,这种解题策略被称为贪心法。 Program Exam25; Const Finp=Input.Txt;
5、 Fout=Output.Txt; Var N,M :Longint; S :Real; P,W :Array1100 Of Integer; Procedure Init; 输出 Var I :Integer; Begin Assign(Input,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:
6、=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 I=WI Then 如果全部可取,则全取 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 主程
7、序 Init; Work; Out; End. 因此,利用贪心策略解题,需要解决两个问题: 首先,确定问题是否能用贪心策略求解;一般来说,适用于贪心策略求解的问题具有以 下特点: 可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题,一般来说需 要一步步的进行多次的贪心选择。在经过一次贪心选择之后,原问题将变成一个相 似的,但规模更小的问题,而后的每一步都是当前看似最佳的选择,且每一个选择 都仅做一次。 原问题的最优解包含子问题的最优解,即问题具有最优子结构的性质。在背包问题 中,第一次选择单位质量最大的货物,它是第一个子问题的最优解,第二次选择剩 4 下的货物中单位重量价值最大的货物
8、,同样是第二个子问题的最优解,依次类推。 其次,如何选择一个贪心标准?正确的贪心标准可以得到问题的最优解,在确定采用贪 心策略解决问题时,不能随意的判断贪心标准是否正确,尤其不要被表面上看似正确的贪心 标准所迷惑。在得出贪心标准之后应给予严格的数学证明。 下面来看看0-1 背包问题。 给定一个最大载重量为M的卡车和N种动物。已知第i 种动物的重量为Wi,其最大价值 为 Vi,设定M ,Wi,Vi均为整数,编程确定一个装货方案,使得装入卡车中的所有动物总价 值最大。 分析:对于N种动物,要么被装,要么不装,也就是说在满足卡车载重的条件下,如何 选择动物,使得动物价值最大的问题。 即确定一组X1,
9、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, 得到价值1
10、50, 然后任意选择A或 B, 由于卡车最大载重为100, 因此卡车不能装载其他动物。 情况 B:不按上述约束条件,直接选择A和 B。可以得到价值80+100=180,卡车装载的 重量为40+50=90。没有超过卡车的实际载重,因此也是一种可行解,显然,这种解比上一 种解要优化。 问题出现在什么地方呢?我们看看图2-18 从图 23 中明显可以看出,情况A,卡车的空载率比情况B 高。也就是说,上面的分析, 只考虑了货物的价值质量比,而没有考虑到卡车的运营效率,因此, 局部的最优化, 不能导 致全局的最优化。 因此,贪心不能简单进行,而需要全面的考虑,最后得到证明。 例 26 排队打水问题 有
11、N个人排队到R个水龙头去打水,他们装满水桶的时间为T1,T2,, , Tn 为整数且各不 图 23 卡车装载货物情况分析 5 相等,应如何安排他们的打水顺序才能使他们花费的时间最少? 分析:由于排队时, 越靠前面的计算的次数越多,显然越小的排在越前面得出的结果越小(可 以用数学方法简单证明,这里就不再赘述),所以这道题可以用贪心法解答,基本步骤: (1)将输入的时间按从小到大排序; (2)将排序后的时间按顺序依次放入每个水龙头的队列中; (3)统计,输出答案。 参考程序: Program Exam26; Const Finp=Input.Txt; Fout=Output.Txt; Var A
12、:Array1100 Of Integer; S :Array1100 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; Procedure Sort(L,R:Integer); 将时间从小到大排序 Var I,J,X,Y :Integer; Begin I:=L; J:=R; X:=A(L+R)
13、 Div 2; Repeat While (AI=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 用贪心法求解 6 Begin Inc(J); If J=M+1 Then J:=1; SJ:=SJ+AI; Min:=Min+SJ; End; Assign(Output,Fout); Rewrite(Output); 输出解答 Writeln
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高中 信息技术 全国青少年 奥林匹克 联赛 教案 贪心
链接地址:https://www.31doc.com/p-5157040.html