贪心算法及其应用doc资料

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

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

3、truct nodeint start;int end; a11111;bool cmp(node x,node y)if(x.end<y.end) return true;else if(x.end=y.end && x.start>y.start) return true;return false;int main()int n,i,j,ans,end;cin>>n;for(i=0;i<n;i+) cin>>ai.start>>ai.end;sort(a,a+n,cmp);ans=0;end=-1e9-100;for(i

4、=0;i<n;i+) if(ai.start>=end) ans+;end=ai.end;cout<<ans<<endl;return 0;5、实验结果：收集于网络，如有侵权请联系管理员删除精品文档四、 实验分析活动安排问题：结束时间越早的活动优先。这个策略是有效的，我们可以证明。假设最优解 OPT中安排了 m个活动，我们把这些活动也按照结束时间由小到大排序，显然是不冲突的。假设排好顺序后，这些活动是a(1) , a(2),a(3).a （ m）假设按照我们的贪心策略，选出的活动自然是按照结束时间排好顺序的，并且也都是不冲突的，这些活动是 b(1), b(2

5、) 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) ， 从而最