高中信息竞赛贪心算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高中信息竞赛-贪心算法,高中信息竞赛-贪心算法高中信息竞赛-贪心算法引 例【问题描述】：在N行M列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共N个数的和最大。,【试题分析】：本题可用贪心策略：选n次,每一次选相应行中的最大值即可。,读入n, m,矩阵数据；,total= 0;,for (i=1;i=n;i+) /对n行进行选择, 选择第i行最大的数,记为k；,total+=k；,输出最大总和total；,引 例,【问题描述】：在N行M列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共N个数的和最大。,【试题分析】：本题可用贪心策略：选n次,每一次选相应行中的最大值即可。,读入n, m,矩阵数据；,total= 0;,for (i=1;i=0&i= 0)将第i种商品全部装入卡车；,else 将m+wi重量的物品i装入卡车;,i= i + 1; /选择下一种商品,程序框架结构,贪心策略求解的问题,因此,利用贪心策略解题,需要解决两个问题：,首先,确定问题是否能用贪心策略求解；一般来说,适用于贪心策略求解的问题具有以下特点：,1.,可通过局部的贪心选择来达到问题的全局最优解,。运用贪心策略解题,一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后,原问题将变成一个相似的,但规模更小的问题,而后的每一步都是当前看似最佳的选择,且每一个选择都仅做一次。,2.,原问题的最优解包含子问题的最优解,即问题具有最优子结构的性质。,在背包问题中,第一次选择单位质量最大的货物,它是第一个子问题的最优解,第二次选择剩下的货物中单位重量价值最大的货物,同样是第二个子问题的最优解,依次类推。,其次,如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解,在确定采用贪心策略解决问题时,不能随意的判断贪心标准是否正确,尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。,应用举例2-删数问题,【问题描述】：,键盘输入一 个高精度的正整数n（nsm;,n=s.length();,for(i=0;im;i+),for(j=0;jsj+1)/删除第一个递减区间的首字符,for(k=j;kn-1;k+)sk=sk+1;,break;,n- -;/否则删除递增区间的最后一个元素,i=0;,while(si=0)i+;/去掉前面的0,for(j=i;jn;j+)coutsj;,应用举例3-纪念品分组2005,Description：元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。,Input：输入文件group.in包含n+2行: 第1行包括一个整数w，为每组纪念品价格之和的上限，第2行为一个整数n，表示购来的纪念品的总件数G 第3-n+2行每行包含一个正整数Pi (5 = Pi j；,void solve(), int i=1,j=n,pair=0;,while(ij), if(ai+aj=w) i+;j-;,else j-;,pair+;,if(i=j) pair+;,coutpairmaxn;,for(i=1;ip;ap+;/桶排序,for(i=max;i=1;i-)/分组,while(ai), ai-;t+;,for(j=max-i;j0;j-),if(aj)aj-;break;,couttendl;,应用举例4-排队打水问题,【问题描述】：有N个人排队到R个水龙头去打水,他们装满水桶的时间为T1,T2,Tn为整数且各不相等,应如何安排他们的打水顺序才能使他们花费的时间最少？,【分析】：由于排队时,越靠前面的计算的次数越多,显然越小的排在越前面得出的结果越小(可以用数学方法简单证明),所以这道题可以用贪心法解答,基本步骤：,1.将输入的时间按从小到大排序；,2.将排序后的时间按顺序依次放入每个水龙头的队列中；,3.统计，输出答案。,应用举例5-取数游戏2341,Description：给出2n(n=100)个自然数(小于等于30000)。将这n个自然数排成一列，游戏双方A和B从中取数，只允许从两端取数。A先取，然后双方轮流取数。取完时，谁取得数字总和最大为取胜方；若双方和相等，属B胜。试问A方是否有必胜策略？,Input：两行，第一行一个整数n；第二行有2*n个自然数。,Output：第一行：若A有必胜策略，则输出yes，否则输出no,Sample Input,4,7 9 3 6 4 2 5 3,Sample Output：yes,方法与技巧,运用贪心策略解题时，有的题目有不止一种可能的贪心标准，但不一定每种贪心标准都能够得到正确的结果。因此，在运用贪心法时，一定要仔细分析，选择恰当的贪心标准。,应用举例6-混合牛奶1648,Description,牛奶包装是一个如此低利润的生意,所以尽可能低的控制初级产品(牛奶)的价格变的十分重要。请帮助快乐的牛奶制造者(merry milk makers)以可能的最廉价的方式取得他们所需的牛奶。快乐的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,快乐的牛奶制造者从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。 给出快乐牛奶制造者的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算快乐的牛奶制造者所要付出钱的最小值。注意:每天农民生产的牛奶的总数对快乐的牛奶制造者来说足够的。,Input,第 1 行:二个整数, n 和 m。 第一个数值,n,(0= n=2,000,000)是快乐的牛奶制造者的一天需要牛奶的数量。 第二个数值,m,(0= m=5,000)是他们可能从农民那买到的数目。 第 2 到 m+1 行:每行二个整数,pi 和 ai。 pi(0= pi=1,000) 是农民 i 牛奶的价格。 ai(0 = ai 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10）。,输 入：N（N 堆纸牌，1 = N = 100）A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000）,输 出：所有堆均达到相等时的最少移动次数。,输入输出样例49 8 17 6屏慕显示：3,应用举例8-,均分纸牌,【试题分析】,我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。因此，我们将相邻两堆间的移动次数限定在一次或零次。,应用举例7-,均分纸牌,【分析】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。,如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。,贪心的经典应用,一、不相交的区间选择, 给n个开区间Si,Fi, 选择尽量多的区间, 使得两两不交。,算法:,首先按照结束时间f1=f2=fn的顺序排序,依次考虑各个活动, 如果没有和已经选择的活动冲突, 就选; 否则就不选。,正确性:,如果不选f1, 假设第一个选择的是fi,则如果fi和f1不交叉则多选一个f1更划算; 如果交叉则把fi换成f1不影响后续选择。,【培训试题】活动选择1649,Description,学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。 现在给出n个活动使用礼堂的起始时间Bi和结束时间Ei(Bi Ei)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。,Input,第一行一个整数n(n=1000)； 接下来的n行，每行两个整数，第一个Bi，第二个是Ei(Bi Ei =32767),Output：,输出最多能安排的活动个数。,Sample Input,11,3 5,1 4,12 14,8 12,0 6,8 11,6 10,5 7,3 8,5 9,2 13,Sample Output：4,二、区间选点, 给,n,个闭区间,ai,bi, 在数轴上选尽量少的点,使每个区间内至少有一个点。,分析：如果可以按照所有区间的结束位置排序,结束位置相同的项,开始位置小的项在前面。从区间1到区间n进行循环,对于当前区间,若集合中的数不能覆盖它,则从区间末尾向前扫描,若当前数没在集合中出现,则将该数加入集合,直至使集合能覆盖该区间为止。,【培训试题】整数区间1650,Description：,一个整数区间A,B,A请编程完成以下任务： 1.从文件中读取区间的个数及其它们的描述； 2.找到满足下述条件的所含元素个数最少的集合中元素的个数,对于每一个区间,都至少有两个不同的整数属于该集合。,Input：首行包括区间的数目n,1=n=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0=a=b=10000,它们是某一个区间的开始值和结束值。,Output：第一行集合元素的个数,对于每一个区间都至少有两个不同的整数属于该区间,且集合所包含元素数目最少。,Sample Input：,4,3 6,2 4,0 2,4 7,Sample Output:4,三、区间覆盖, 给,n,个闭区间,ai,bi, 选择尽量少的区间覆盖一个给定线段,s,f,。,算法:,对于每个区间, 删除在s, f之外的部分, 并按a1=a2=an的顺序排序, a相同时按b从大到小排序. 从左到右扫描, 如果当前区间可以覆盖,新,的部分, 选择此线段。,【培训试题】线段覆盖1893,Description:,给出数轴上N条线段,第i条线段用两个数表示Ai,Bi(AiBi),表示从Ai到Bi的一条线段。现在请求出它们覆盖数轴上的多长距离 (Ai、Bi的绝对值可能达到109) 。,Input:,第一行：N,以后N行，每行两个数：AiBi,Output:,一个数，表示覆盖长度,Sample Input,3,2 8,-1 1,5 10,Sample Output：,10,四、流水作业调度, n个作业要在由两台机器M1和M2组成的流水线上完成加工. 每个作业i必须先在M1上然后在M2上加工, 时间分别为ai和bi；, 确定这n个作业的加工顺序, 使得从第一个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小；, 直观上, 最优调度一定让M1没有空闲, M2的空闲时间尽量少；,Johnson算法.,设N1为a=b的作业集合, 将N1的作业按a非减序排序, N2中的作业按照b非增序排序, 则N1作业接N2作业构成最优顺序., 程序易于实现, 时间O(nlogn), 关键在于正确性证明。,例：加工生产调度,【问题描述】：某工厂收到了n个产品的订单,这n个产品分别在A、B两个车间加工,并且必须先在A车间加工后才可以到B车间加工。,某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序,才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。,【输入】：第一行仅个数据n(0n1000),表示产品的数量。接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。,【输出】：第一行一个数据,表示最少的加工时间；第二行是一种最小加工时间的加工顺序。,【样例输入】：,5,3 5 8 7 10,6 2 1 4 9,【样例输出】：,34,【算法分析】：,本题求一个加工顺序使得加工总时间最短,要使时间最短,则就是让机器的空闲时间最短。一旦A机器开始加工,则A机器将会不停的进行作业，关键是B机器在加工过程中,有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待,最后一个部件在B机器上加工,A机器也在等待B机器的完工。,可以大胆猜想,要使总的空闲的最少,就要把在A机器上加工时间最短的部件最先加工,这样使得B机器能以最快的速度开始加工;把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：,设Mi=minai, bi,将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。,例如：N=5,（a1，a2，a3，a4，a5）=（3，5，8，7，10）,（b1，b2，b3，b4，b5）=（6，2，1，4，9）,则（m1，m2，m3，m4，m5）=（3，2，1，4，9）,排序之后为（m3，m2，m1，m4，m5）,处理m3：m3=b3 m3排在后面；加入m3之后的加工顺序为( ， ， ， ，3)；,处理m2：m2=b2 m2排在后面；加入m2之后的加工顺序为( ， ， ，2，3)；,处理m1：m3=a1 m1排在前面；加入m1之后的加工顺序为(1， ， ，2，3)；,处理m4：m4=b4 m4排在后面；加入m4之后的加工顺序为(1， ，4，2，3)；,处理m5：m5=b5 m5排在后面；加入m5之后的加工顺序为(1，5，4，2，3)；,则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。,问题是这种贪心策略是否正确呢？还需证明。,算法流程如下：,for I := 1 to N do 求M数组,if AI BI then MI := AI,else MI := BI；,将M从小到大排序；,S := 1; T := N; 首位指针初始化,for I := 1 to N do,if 对于第I小的工序J，若AJ BJ then,begin,OrderS := J; 将工序J插在加工序列的前面,S := S + 1;,end,else begin,OrderT := J; 将工序J插在加工序列的后面,T := T - 1;,end;,五、任务时间表问题, 有n个任务, 每个任务都需要1个时间单位执行. 任务i的截止时di(1=di=n)表示要求任务i在时间di前结束. 误时惩罚wi表示若任务i未在时间di之前结束将导致wi的惩罚;, 确定所有任务的执行顺序, 使得最惩罚最小;,分析： 称在限期内完成的任务为早任务, 收到罚款的任务为迟任务. 如果早任务紧跟在迟任务之后, 交换之后总罚款不变；, 假设对于相邻两个早任务i和i+1. 由于两个任务都是早任务, 因此t,j+1,d,i+1,则t,i+1,=d,i+1,d,i, 交换以后显然i+1的时间更早, 仍然是早任务; i的时间t,i,=t,i+1,d,i,仍然是早任务, 总罚款不变；, 规范形式: 所有早任务在迟任务前, 且按限期非递减排序., 关键: 选哪些作为早任务?, 不是任选一些任务作为早任务都是可行的. 对于一个早任务集合S, 如何判断它是否可行呢? 只需要对S内的元素按限期非递减排序, 然后一一放置；, 贪心算法：先把罚款,E,中元素按照权值从大到小排序为,e,1,e,2,按照,e,1,e,2,的顺序，尝试添加到当前集合,S,里；, 如果添加之后,S,仍是独立集，则添加成功, 如果,S,不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此不能进行此添加操作；,Description:一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;。,单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:,1.包含n个单位时间任务的集合S=1,2,n;,2.n个取整的期限d1,dn,(1d,n),任务i要求在di前完成;,3.n个非负的权(或罚款)w1,wn。如果任务i没在时间di之前结束, 则导致罚款wi;,要求找出S的一个调度,使之最小化总的罚款。,Input:第一行为一个n(n=100)，表示n个任务，以后n行，每行两个数di和wi分别表示期限和罚款,Output:最小化总的罚款,罚款问题,Sample Input,6,6 10,4 70,3 40,2 60,4 50,1 30,4 20,Sample Output:,50,【算法分析】：,要使罚款最少,我们显然应尽量完成wi值较大的工作,此时,我们可以将工作按wi从大到小进行排序,然后按排好的顺序依次对工作进行安排,安排的规则为:要使处理工作i的时间既在di之内,又尽量靠后;如果di之内的时间都已经排满,就放弃此项工作。,例如: 任务i 1 2 3 4 5 6 7,期限di 4 2 4 3 1 4 6,罚款wi 70 60 50 40 30 20 10,最初,我们设所有n个时间空位都是空的。然后按罚款的单调递减顺序(任务1,任务2,任务3,任务4,任务5,任务6,任务7)对各个子任务作贪心选择。在考虑任务j时,如果有一个恰处于或前于dj的时间空位仍空着,则将任务j 赋与最近的这样的空位,并填入; 如果不存在这样的空位,则将任务j赋与一个还未被占的、最近的空位。,按上述贪心策略选择了任务1,2,3,4,7,放弃任务5,6。最终的最优调度为2,4,3,1,7,5,6,其总的罚款为W5+W650。,六、最优合并问题, 有n个正整数, 每次可以合并两个相邻的数，得到他们的和, 代价为相加后的新数., 按如何的顺序把所有的数合并成一个, 使得代价总和尽量小?, 贪心法: 每次采取代价最少的合并方案, 不一定得到最优解! 最优解为74,Description：在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。 例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。,【培训试题】合并果子1059,Input：,输入包括两行,第一行是一个整数n(1n=10000),表示果子的种类数。第二行包含n个整数,用空格分隔,第i个整数ai(1ai=20000)是第i种果子的数目。,Output：,输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于231。,Sample Input：,3 1 2 9,Sample Output：,15,【数据规模】,对于30的数据,保证有n=1000： 对于50的数据,保证有n=5000； 对于全部的数据,保证有nn;,for(i=1;im;cm+;bi=2000000000;,m=0;,for(i=1;i=20000;i+),while(ci) a+m=i;ci-;,for(i=1;i=n-1;i+), minn=2000000000;,if(ax+ax+1minn,if(ax+byminn,if(by+by+1minn,sum+=minn;b+blen=minn;,if(p=1) x=x+2;,if(p=2)x+;y+;,if(p=3) y=y+2;,coutsumendl;,核心代码,七、Huffman编码, 给n个字符的频率，设计Huffman编码, 即给出每个字符的编码串(01串), 使得任意两个编码串互不为前缀, 且总编码长度(每个字符的频率与串长乘积之和)最小,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在,20%,90%,之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用,0,，,1,串表示各字符的最优表示方式。,给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。,例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为：,（,451+133+123+163+94+54,）,1000=224,000,。,八、最小生成树,九、单源最短路径,汇报结束,谢谢大家,!,请各位批评指正,