贪心算法及其应用doc资料.docx

《贪心算法及其应用doc资料.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、贪心算法及其应用精品文档湖州师范学院实验报告课程名称：算法实验三：贪心算法一、实验目的1、理解贪心算法的概念，掌握贪心算法的基本要素。2、掌握设计贪心算法的一般步骤，针对具体问题，能应用贪心算法求解。二、实验内容1、问题描述活动安排问题设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

2、活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。2、数据输入：文件输入或键盘输入。3、要求：1）完成上述两个问题中1个或全部，时间为1次课。2）独立完成实验及实验报告。三、实验步骤1、理解方法思想和问题要求。2、采用编程语言实现题目要求。3、上机输入和调试自己所写的程序。4、附程序主要代码：2、活动规划问题#include#include收集于网络，如有侵权请联系管理员删除精品文档#includeusingnamespacestd;structnode{ints

3、tart;intend;}a[11111];boolcmp(nodex,nodey){if(x.endy.start)returntrue;returnfalse;}intmain(){intn,i,j,ans,end;cin>>n;for(i=0;i>a[i].start>>a[i].end;sort(a,a+n,cmp);ans=0;end=-1e9-100;for(i=0;i=end){an

4、s++;end=a[i].end;}}cout<

5、)….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)冲突么？

6、 不冲突，因为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)，从而最优解和我们贪心得到的解多了一个相同的，经过一个一个替换，我们可以把最优解完全替换成我们贪心策略得到的解。从而证明了这个贪心策略的最优性。收集于网络，如有侵权请联系管理员删除