《贪心算法及其应用.docx》由会员分享，可在线阅读，更多相关《贪心算法及其应用.docx（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除湖州师范学院实验报告课程名称：算法实验三： 贪心算法一、 实验目的1、 理解贪心算法的概念，掌握贪心算法的基本要素。2、 掌握设计贪心算法的一般步骤，针对具体问题，能应用贪心算法求解。二、 实验内容1、问题描述活动安排问题设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动
2、j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。2、数据输入：文件输入或键盘输入。3、要求：1）完成上述两个问题中1个或全部，时间为 1 次课。2）独立完成实验及实验报告。三、 实验步骤1、 理解方法思想和问题要求。2、 采用编程语言实现题目要求。3、 上机输入和调试自己所写的程序。4、附程序主要代码：2、活动规划问题#include#include #include using namespace std; struct node int start; int end; a11111; bool cmp(node x,node y) if(x.endy.start) ret
3、urn true; return false; int main() int n,i,j,ans,end; cinn; for(i=0;iai.startai.end; sort(a,a+n,cmp); ans=0; end=-1e9-100; for(i=0;i=end) ans+; end=ai.end; coutansendl; return 0; 5、实验结果：四、 实验分析活动安排问题：结束时间越早的活动优先。这个策略是有效的，我们可以证明。假设最优解OPT中安排了m个活动，我们把这些活动也按照结束时间由小到大排序，显然是不冲突的。假设排好顺序后，这些活动是a(1) , a(2),
4、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)， 从而最优解和我们贪心得到的解多了一个相同的，经过一个一个替换，我们可以把最优解完全替换成我们贪心策略得到的解。 从而证明了这个贪心策略的最优性。【精品文档】第 3 页