第4章贪心算法.ppt

第4章贪心算法理解贪心算法的概念。掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。找币问题有位顾客买了两斤苹果，需付3元7角，实付10元，你需找零6元3角。假设你抽屉里有一些硬币，面值分别为：2元5角、1元、5角和1角，现在问题是：怎么找币最快（取硬币次数最少）？问题描述：M=6.3，n=4V={2.5,1.0,0.5,0.1}（分量用vi表示）X={x1,x2,x3,x4}（xi=0,i=1~4）即求:0-1背包问题找币问题找币问题可用动态规划法来求解，但还有一种更简单可行的方法。先取2.52枚价值2.5+2.5=5.0余6.3-5=1.3再取1.01枚价值1.0余1.3-1=0.3不取0.50枚因为0.50.3再取0.13枚价值0.1×3=0.3余0.3-0.3=0找零完毕。得最优解X={2,1,0,3}，共需最少的硬币数6枚。在不超余额的前提下，每次都找最大面值的硬币，这种找币的方法叫做贪心算法。贪心算法 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心算法并不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似解。4.1活动安排问题新学期来临，为迎接新生，各院系都要举办迎新晚会。时间将近，各院系在申请使用学院礼堂进行彩排。为了提高礼堂使用率，决定白天不间断的开放，各院系可以上报各自使用的时间区间（开始时间以及终止时间，时间长短不限），由礼堂管理人员安排尽可能多的院系在同一天里彩排。请根据以下时间段尽可能多安排几个院系：[8:00,10:30),[9:00,11:30),[7:00,11:00),[11:30-14:00),[12:00,13:30),[13:00,15:30),[15:00,16:00),[14:30,16:00),[16:00,18:00)4.1活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的典型例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。4.1活动安排问题4.1活动安排问题将各活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非减序排列：f1=f2=f3......=fn即需要先对各活动按结束时间排序。如：[2,3),[1,4),[3,5),[1,2)按结束时间排序后：[1,2),[2,3),[1,4),[3,5)4.1活动安排问题templateclassTypevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;//加入最早结束的活动intj=1;//刚加入集合的活动号for(inti=2;i=n;i++){if(s[i]=f[j]){A[i]=true;j=i;}elseA[i]=false;}}//j用以记录最近一次加入到集合A中的活动4.1活动安排问题 算法GreedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。4.1活动安排问题算法GreedySelector的效率极高。当输入的活动已按结束时间的非减序排列时，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。4.1活动安排问题例：