贪心算法课件1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,贪心算法,贪心方法的基本思想,贪心是一种解题策略，也是一种解题思想,使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优,利用贪心策略解题，需要解决两个问题：,该题是否适合于用贪心策略求解,如何选择贪心标准，以得到问题的最优解,【,引例,】,在一个,NM,的方格阵中，每一格子赋予一个数（即为权），规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。,我们以,23,的矩阵为例：,若按,贪心策略,求解，所得路径为：,1346,；,若按,动态规划,求解，所得路径为：,12106,。,贪心法的特点,1.,贪心选择性质：,算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。,2.,最优子结构性质：,算法中每一次都取得了最优解,(,即局部最优解,),，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。,但并不是所有,具有,最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法,动态规划（例如,“,0-1,背包问题,”,与,“,部分背包问题,”,）,【,问题,1】,部分背包问题,给定一个最大载重量为,M,的卡车和,N,种食品，有食盐，白糖，大米等。已知第,i,种食品的最多拥有,Wi,公斤，其商品价值为,Vi,元,/,公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。,【,分析,】,因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。,方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。,【,问题,2】0/1,背包问题,给定一个最大载重量为,M,的卡车和,N,种动物。已知第,i,种动物的重量为,Wi,，其最大价值为,Vi,，设定,M,，,Wi,，,Vi,均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。,【,分析,】,按贪心法：每次选价格最大的装载。很明显有反例：设,N=3,卡车最大载重量是,100,三种动物,A,、,B,、,C,的重量分别是,40,50,70,其对应的总价值分别是,80,、,100,、,150,。,贪心策略与其他算法的区别,1.,贪心与递推：,与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。,2.,贪心与动态规划：,与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。,几个简单的贪心例子,贪心策略,例题,1,：删数问题,键盘输入一个高精度的正整数,n,（,n,从取,3,张牌放到,(9 11 10,10,)-,从取,1,张牌放到,(10 10,10,10,）。,分析：,【,试题分析,】,我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。,【,思路点拨,】,如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成,0,，那就意味着成功了一半！,从第,i,堆移动,-m,张牌到第,i+1,堆，等价于从第,i+1,堆移动,m,张牌到第,i,堆,步数是一样的。,注意最左边的,0,和最右边的,0,不能算在内，如,0,0,1,-3,4,0,-1,0,0,扩展,1,：,若题目中的纸牌排成一个环状，应如何处理呢？,其中,n=1000,。,扩展,2,：,有,n,个小朋友坐成一圈，每人有,a,i,个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为,1,。求使所有人获得均等糖果的最小代价。,【,数据规模,】,对于,30%,的数据,n=1000,；,对于,100%,的数据,n=1000000,贪心的经典应用,（一）、三个区间上的问题,1,、选择不相交区间问题,2,、区间选点问题,3,、区间覆盖问题,（二）、两个调度问题,1,、流水作业调度问题,2,、带限期和罚款的单位时间任务调度,（三）,Huffman,编码,（四）,最优合并问题,1,、选择不相交区间问题,给定,n,个开区间,(,ai,bi),，选择尽量多个区间，使得这些区间两两没有公共点。,【,算法实现,】,首先按照,b1=b2=,=,bn,的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。,贪心策略：取第一个区间；,【,正确性,】,：,如果不选,b1,，假设第一个选择的是,bi,，则如果,bi,和,b1,不交叉则多选一个,b1,更划算；如果交叉则把,bi,换成,b1,不影响后续选择。,例题,5,：活动安排,设有,n,个活动的集合,E=1,2,.,n,，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动,i,都有一个要求使用该资源的起始时间,si,和一个结束时间,fi,，且,si,fi,。如果选择了活动,i,，则它在半开时间区间,si,fi,),内占用资源。若区间,si,fi,),与区间,sj,fj,),不相交，则称活动,i,与活动,j,是相容的。也就是说，当,fi,=,si,时，活动,i,与活动,j,相容。选择出由互相兼容的活动组成的最大集合。,2,、区间选点问题,给定,n,个闭区间,ai,bi,，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。,【,算法,】,：,首先按照,b1=b2=,=,bn,排序。每次标记当前区间的右端点,X,，并右移当前区间指针，直到当前区间不包含,X,，再重复上述操作。,贪心策略：取最后一个。,例题,6,：种树（,NOIP,模拟试题）,一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为,1.n,。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码,b,e,t,。这三个数表示该居民想在,b,和,e,之间最少种,t,棵树。当然，,b=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求,t=s,的,bi,的最大值即可。,例题,7,：区间（,SDOI2005,）,现给定,n,个闭区间,ai,bi,，,1=i=n,。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间,a,b,和,c,d,是按照升序排列的，那么我们有,ab=c=d,。任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。,练习试题：喷水装置,有一块草坪，长为,L,，宽为,w,；,在它的中心线上装有,n,个点状的喷水装置，效果是让以它为中心半径为,ri,的圆被润湿，选择尽量少的喷水装置把整个草坪全部润湿。,1,、流水作业调度问题,分析,2,、带限期和罚款的单位时间任务调度,旅行家的预算,一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离,D1,、汽车油箱的容量,C,（以升为单位）、每升汽油能行驶的距离,D2,、出发点每升汽油价格,P,和沿途加油站数,N,（,N,可以为零），油站,i,离出发点的距离,Di,、每升汽油价格,Pi,（,i=1,，,2,，,，,N,）。,计算结果四舍五入至小数点后两位。,如果无法到达目的地，则输出“,No Solution”,。,样例：,Input,D1=275.6C=11.9D2=27.4 P=2.8 N=2,油站号,I,离出发点的距离,Di,每升汽油价格,Pi1102.02.92220.02.2,Output,26.95,（该数据表示最小费用）,分析：,需要考虑如下问题：,出发前汽车的油箱是空的，故汽车必须在起点（,1,号站）处加油。加多少油？,汽车行程到第几站开始加油，加多少油？,可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：,对于加油站,I,，下一个加油站,J,可能第一个是比油站,I,油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。,对于第一种情况，则油箱需要（,d,（,j,）,-d,（,i,）,/m,加仑汽油。对于第二种情况，则需将油箱加满。,算法,I:=1 ,汽车出发设定为第,1,个加油站,L:=C*D2,；,油箱装满油能行驶的距离,repeat,在,L,距离以内，向后找第一个油价比,I,站便宜的加油站,J,；,if J,存在,then,if I,站剩余油能到达,J then,计算到达,J,站的剩油,else,在,I,站购买油，使汽车恰好能到达,J,站,else,在,I,站加满油；,I:=J,；,汽车到达,J,站,until,汽车到达终点；,贪心方法的推广,贪心与其它算法结合,搜索的最优化剪枝（,生日蛋糕）,优化动态规划（,Peter,的快餐店）,贪心方法与解题策略,最优方法不一定是最好方法,想不到最优解法就用较优解法,贪心小结,:,贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。,并且，贪心与其他算法的结合，可以对其他算法起到优化作用。,