贪心算法及其应用

湖州师范学院实验报告课程名称：算法实验三：贪心算法一、实验目的1、理解贪心算法的概念，掌握贪心算法的基本要素。2、掌握设计贪心算法的一般步骤，针对具体问题，能应用贪心算法求解。二、实验内容1、问题描述活动安排问题设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。2、数据输入：文件输入或键盘输入。3、要求：1）完成上述两个问题中1个或全部，时间为1次课。2）独立完成实验及实验报告。三、实验步骤1、理解方法思想和问题要求。2、采用编程语言实现题目要求。3、上机输入和调试自己所写的程序。4、附程序主要代码：2、活动规划问题#includestdio.h#includeiostream#includealgorithmusingnamespacestd;structnode{intstart;intend;}a[11111];boolcmp(nodex,nodey){if(x.endy.end)returntrue;elseif(x.end==y.end&&x.starty.start)returntrue;returnfalse;}intmain(){intn,i,j,ans,end;cinn;for(i=0;in;i++)cina[i].starta[i].end;sort(a,a+n,cmp);ans=0;end=-1e9-100;for(i=0;in;i++){if(a[i].start=end){ans++;end=a[i].end;}}coutansendl;return0;}5、实验结果：四、实验分析活动安排问题：结束时间越早的活动优先。这个策略是有效的，我们可以证明。假设最优解OPT中安排了m个活动，我们把这些活动也按照结束时间由小到大排序，显然是不冲突的。假设排好顺序后，这些活动是a(1),a(2),a(3)….a（m）假设按照我们的贪心策略，选出的活动自然是按照结束时间排好顺序的，并且也都是不冲突的，这些活动是b(1),b(2)…b(n)问题关键是，假设a(1)=b(1),a(2)=b(2)….a(k)=b(k)，但是a(k+1)!=b(k+1)，回答几个问题：(1)b(k+1)会在a(k+2),a(k+3),….a(m)中出现么？不会。因为b(k+1)的结束时间是最早的，即f(b(k+1))=f(a(k+1)),而a(k+2),a(k+3),….a(m)的开始时间和结束时间都在f(a(k+1))之后，所以b(k+1)不在其中。(2)b(k+1)和a(1),a(2),….a(k)冲突么？不冲突，因为a(1),a(2),….a(k)就是b(1),b(2),….b(k)(3)b(k+1)和a(k+2),a(k+3),….a(m)冲突么？不冲突，因为f(b(k+1))=f(a(k+1))，而a(k+2),a(k+3),….a(m)的开始时间都在f(a(k+1))之后，更在f(b(k+1))之后。因此我们可以把a(k+1)换成b(k+1)，从而最优解和我们贪心得到的解多了一个相同的，经过一个一个替换，我们可以把最优解完全替换成我们贪心策略得到的解。从而证明了这个贪心策略的最优性。