15 贪心算法

15 贪心算法算法导论基于人性，理想永远只属于少数人。可是，少数人的理想经常会推动时代，为多数人谋取福利。 15 贪心算法 Greedy Algorithms • 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 • 当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解...

算法导论基于人性，理想永远只属于少数人。可是，少数人的理想经常会推动时代，为多数人谋取福利。 15 贪心算法 Greedy Algorithms • 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 • 当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 15.1 活动安排问题 • 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 • 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如教室等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si 方法：选择一个活动ai，使其具有最早的结束时间。 i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14 void GreedySelector(int n, int s[], int f[], bool A[]) { A[1]=true; int j=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { A[i]=true; j=i; } else A[i]=false; } } • 由于输入的活动以其完成时间的非减序排列，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入集合 A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 • 算法GreedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn) 的时间重排。 • 算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。 • 若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fj，则不选择活动i，否则选择活动i加入集合A中。 • 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法 GreedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。 15.2 贪心算法的基本要素 • 贪心算法是通过做一系列的选择来给出某一些问题的最优解。对算法中的每一个决策点，做一个当时（看起来是）最佳的选择。但这种启发式策略并不是总能产生出最优解。 • 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢 ?这个问题很难给予肯定的回答。 • 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 1、贪心选择性质 • 贪心选择性质：所求问题的全局最优解可以通过一系列局部最优（即贪心）选择来达到。也就是说，在考虑如何选择时，我们只考虑对当前问题最佳的选择，而不考虑子问题的结果。 • 这一性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 • 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 • 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2、最优子结构性质 • 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 • 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 3、贪心算法与动态规划的差异 • 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。（1）0-1背包问题 • 给定n种物品和一个背包。物品i的重量是 Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? • 在选择装入背包的物品时，对每种物品i只有2种选择：装入背包（=1）或不装入背包（=0）。不能将物品i装入背包多次，也不能只装入部分的物品i。（2）背包问题 • 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包（1≤i≤n）。 • 这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0- 1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤： • 首先计算每种物品单位重量的价值Vi/Wi。 • 然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。 • 若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。 • 依此策略一直地进行下去，直到背包装满为止。 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); //按Vi/W i递减排序 for (int i=1;i<=n;i++) x[i]=0; float c=M; //c为背包的剩余容量 for (int i=1;i<=n;i++) { if (w[i]>c) break; //若第i件物品不能全部装入，则只能部分装入 x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } • 算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O(nlogn)。 • 为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。 • 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1 背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 • 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。例如：电梯 • Zsoft公司是一家位于高科大厦的软件公司。而且大厦里的工作人员工作非常努力。 • 但是大厦里的电梯经常让他们发疯。为什么？原来高科大厦里只有一部电梯，但这里确有数百个公司。每天早上，人们必须浪费很多时间等电梯。 • Zsoft里有一个聪明的家伙，想要改变这种状况。他想找到一种方法，让电梯工作的更有效。不过这可并非易事。 • 高科大厦有H层。电梯上升一层需要4秒时间。 • 也就是说，电梯从1楼运行到n楼需要(n- 1)*4秒，如果中间不停的话。 • 而电梯停一次需要10秒时间。所以，考虑电梯停留时间的话，从一楼运行到n楼需要 (n-1)*4+(n-2)*10 秒。即每层都停的时间。 • 另一方面，员工走楼梯(上楼或下楼)，一层需要20秒。走n层楼需要花费(n-1)*20秒的时间。显然，这不是个好主意。所以，一些人选择坐电梯到离他们办公室最近的一层。 • 经过很长时间的思考，这个人终于找到一种方法，以改变这种状况。他把自己的想法告诉开电梯的人：首先，开电梯的人向人们询问他们要去的楼层。然后他设计一种停留方案，使最后一个人到达他办公室所在楼层的时间最小化。 • 举例来说，如果电梯需要停在4楼、5楼和 10楼，停留的计划会是：电梯停在4楼和10 楼。因为电梯从1楼到4楼需要花3*4=12秒的时间，然后，到5楼的人步行1层，需要花费3*4+20=32秒的时间，电梯经过10秒的停留后，运行到10楼需要3*4+10+6*4=46秒的时间。也就是，最后一个到达的人需要花费 46秒的时间。这对所有人都是一个好主意。 • 现在，你被要求写一个程序，以帮助开电梯的人制订停留计划，以最小化最后一个人到达他所在楼层的时间。 • 输入： – 输入包含多组数据，每组数据在单独的一行上，如下所示： – n f1 f2 ... fn – 其含义为，总共有n层需要停留，n=0时程序结束。然后，f1 f2 … fn是电梯需要停留的楼层 (1<=n<=30000, 2<=f1< f2 ... fn<=30000) 。数字之间用一个空格隔开。 • 输出： – 对每一组数据，在单独的一行上输出最后一个人到达所需的时间。 • 输入样例： – 3 4 5 10 – 1 2 – 0 • 输出样例： – 46 – 4 题目分析 • 如果知道停几层，则可以枚举这些层数，但这样做是指数级的算法。 • 我们知道最省时的时间t一定在两种极端情况下： • 一种情况电梯一路不停，则达到n层的时间是(n- 1)*4，这种情况下可能不满足要求； • 另一种极端情况是每层必停，则时间为(n- 1)*4+(n-2)*10 。 • 所以我们可以搜索时间t，在给定该时间t后判定该时间能否使得所有人到达自己的楼层，搜索范围在上述两个极端情况下。 • 对于每个给定的时间t，我们可以使用贪心法确定是否可以在时间t内让所有人都到达目的层。显然，每一次电梯都尽量往上开，贪心的标准是电梯尽量少停。 • 比如说现在第i层有人要下，电梯应该在哪一层停靠呢？假设电梯已经停靠了n次，那么我们让电梯在第j=[(t-10*n+20*i+4)/24]层停靠即可。注意此时若j #include const int M=30001; bool ind[M]; int n; int solve(int t){ // 判定时间 t 之内所有人是否都能到达目标层 int i,j,now=0,num=0; i=t/20+2; // i 层以下的人直接走楼梯，哈哈 while(i<=n){ while(i<=n && ind[i]==false){ // i 层没人时不用理 i++; } if((i-1)*4+10*num>t) return 0; // 电梯无法在时间 t 之内到达 i 层 j=(t-10*num+20*i+4)/24; // 电梯在第 j 层停靠最好 i=(t-10*num+16*j+4)/20+1; // 电梯 i 层以下的都已经搞定 num++; //已经停靠的次数 } return 1; } main(){ int i,j,min,max,mid,t; // freopen("data.txt","r",stdin); while(1){ scanf("%d",&t); if(t==0) break; memset(ind,false,sizeof(ind)); n=-1; // 读入数据 for(i=0;in) n=j; ind[j]=true; } // 二分法，查找区间为 [min,max]，其中min总是不可行的，max则为可行解 min=0;max=14*(n-1); while(min

                    本文档为【15  贪心算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

15 贪心算法

你可能还喜欢