|
信息学竞赛常用算法与策略：贪心策略 在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。 7.1 贪心策略的定义 贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。 其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。 例1：在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。 本题可用贪心策略：选n次，每一次选相应行中的最大值即可。 例2：在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。 本题用贪心策略不能得到最优解，我们以2×4的矩阵为例。 若按贪心策略求解，所得路径为：1,3,4,6；若按动态规划法求解，所得路径为：1,2,10,6。 例3:设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短? 本题不能用贪心算法求解:理由是若n=3,m=6 各作业的时间分别是11 7 5 5 4 7 用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是14,但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过15,给搜索提供了方便。 总之： 1. 不能保证求得的最后解是最佳的； 2. 只能用来求某些最大或最小解问题； 3. 能确定某些问题的可行解的范围，特别是给搜索算法提供了依据。 7. 2 贪心策略的特点 贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点： 1、贪心选择性质： 所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。 2、局部最优解： 我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，但贪心策略比动态规划时间效率更高站用内存更少，编写程序更简单。 7.3 典型例题与习题 例4：背包问题： 有一个背包，背包容量是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<=M( M=150) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占空间最小的物品装入是否能得到最优解？ （3）每次选取单位容量价值最大的物品，成为解本题的策略。 程序如下： program beibao; const m=150; n=7; var xu:integer; i,j:integer; goods:array[1..n,0..2] of integer; ok:array[1..n,1..2] of real; procedure init; var i:integer; begin xu:=m; for i:=1 to n do begin write('Enter the price and weight of the ',i,'th goods:'); goods[i,0]:=i; read(goods[i,1],goods[i,2]); readln; ok[i,1]:=0; ok[i,2]:=0; end; end; procedure make; var bi:array[1..n] of real; i,j:integer; temp1,temp2,temp0:integer; begin for i:=1 to n do bi[i]:=goods[i,1]/goods[i,2]; for i:=1 to n-1 do for j:=i+1 to n do begin if bi[i] temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2]; goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2]; goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2; end; end; end; begin init; make; for i:=1 to 7 do begin if goods[i,2]>xu then break; ok[i,1]:=goods[i,0]; ok[i,2]:=1; xu:=xu-goods[i,2]; end; j:=i; if i<=n then begin ok[i,1]:=goods[i,0]; ok[i,2]:=xu/goods[i,2]; end; for i:=1 to j do writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1); end. 例5：旅行家的预算问题： 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。 计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer" 若输入： d1=275.6c=11.9d2=27.4p=8n=2 d[1]=102 p[1]=2.9 d[2]=220 p[2]=2.2 output 26.95 本问题的贪心策略是：找下一个较便宜的油站，根据距离确定加满、不加、加到刚好到该站。 程序如下: program jiayou; const maxn=20231; zero=1e-16; type jd=record value,way,over:real; end; var oil:array[1..maxn] of ^jd; n:integer; d1,c,d2,cost,maxway:real; function init:boolean; var i:integer; begin new(oil[1]); oil[1]^.way:=0; read(d1,c,d2,oil[1]^.value,n); maxway:=d2*c; for i:=2 to n+1 do begin new(oil[i]); readln(oil[i]^.way,oil[i]^.value); oil[i]^.over:=0; end; inc(n,2); new(oil[n]); oil[n]^.way:=d1; oil[n]^.value:=0; oil[n]^.over:=0; for i:=2 to n do if oil[i]^.way-oil[i-1]^.way>maxway then begin init:=false; exit end; init:=true; end; procedure buy(i:integer;miles:real); begin cost:=cost+miles/d2*oil[i]^.value; end; procedure solve; var i,j:integer; s:real; begin i:=1;j:=i+1; repeat s:=0.0; while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do begin inc(j); s:=s+oil[j]^.way-oil[j-1]^.way end; if s<=maxway+zero then if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else begin buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over); oil[j]^.over:=0.0; end else begin buy(i,maxway-oil[i]^.over); j:=i+1; oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way); end; i:=j; until i=n; end; begin cost:=0; if init then begin solve; writeln(cost:0:2); end else writeln('No answer'); end. 例6:n个部件,每个部件必须经过先A后B两道工序。 以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？ 输入： 5 输出：34 1 5 4 2 3 本问题的贪心策略是A机器上加工短的应优先，B机器上加工短的应靠后。 程序如下： program workorder; const maxn=100; type jd=record a,b,m,o:integer; end; var n,min,i:integer; c:array[1..maxn] of jd; order:array[1..maxn] of integer; procedure init; var i:integer; begin readln(n); for i:=1 to n do read(c[i].a); readln; for i:=1 to n do read(c[i].b); readln; for i:=1 to n do begin if c[i].a c[i].o:=i; end; end; procedure sort; var i,j,k,t:integer; temp:jd; begin for i:=1 to n-1 do begin k:=i;t:=c[i].m; for j:=i+1 to n do if c[j].m if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end end; end; procedure playorder; var i,s,t:integer; begin fillchar(order,sizeof(order),0); s:=1; t:=n; for i:=1 to n do if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end else begin order[t]:=i;t:=t-1;end; end; procedure calc_t; var i,t1,t2:integer; begin t1:=0;t2:=0; for i:=1 to n do begin t1:=t1+c[order[i]].a; if t2 t2:=t2+c[order[i]].b; end; min:=t2; end; begin init; sort; playorder; calc_t; writeln(min); for i:=1 to n do write(c[order[i]].o,' '); writeln; end. 习题： 1.最佳浏览路线问题: 某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-１００到１００的整数，所有林荫道不打分。所有分值不可能全是负值。 例如下图是被打过分的某旅游区的街道图： 阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。 2..删数问题 键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。 参考程序： 1.最佳游览路线问题 输入数据：输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1≤M≤100），N表示有多少条林荫道（1≤N≤20230）。接下里的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。 输出文件：输出文件是 OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳浏览路线的总分值。 Program Tour; var m,n:integer; {M为旅游街数，N为林荫道数} data:array[1..20230] of -100..100;{data是由相邻两条林荫道所分} procedure Init; {隔的旅游街的最大分值} var a,b,c:integer; f1:text; begin assign(f1,'input.txt'); reset(f1); read(f1,m,n); for a:=1 to n-1 do read(f1,data[a]);{读取每一段旅游街的分值} for a:=2 to m do for b:=1 to n-1 do begin read(f1,c); if c>data[b] then data[b]:=c;{读取每一段旅游街的分值，并选择} end; {到目前位置所在列的最大分值记入数组data} close(f1); end; procedure Done; var a,sum,result,c:integer; f2:text; begin result:=0; sum:=0; a:=0; while (a begin inc(a); {从数组的第一个数据开始累加，将累加所} sum:=sum+data[a]; {得到的最大分值记入result} if sum>result then result:=sum; if sum<0 then sum:=0; {若当前累加值为负数，则从当前状态起从新} end; {累加} assign(f2,'output.txt'); rewrite(f2); writeln(f2,result); close(f2); end; begin Init; Done; end. 2.删数问题的源程序： 输入数据：一个高精度正整数N，所删除的数字个数S。 输出数据：去掉的数字的位置和组成的新的正整数。 Program Delete_digit; Var n:string;{n是由键盘输入的高精度正整数} s,a,b,c:byte;{s是所要删除的数字的个数} data:array[1..200] of 0..9; {记录删除的数字所在位置} begin readln(n); readln(s); for a:=1 to s do for b:=1 to length(n) do if n[b]>n[b+1] then{贪心选择} begin delete(n,b,1); data[a]:=b+a-1; {记录所删除的数字的位置} break; end; while n[1]='0' do delete(n,1,1);{将字符串首的若干个“0”去掉} writeln(n); for a:=1 to s do writeln(data[a],' '); end. | 
