湖州师范学院实验报告
课程名称:算法
实验三: 贪心算法
一、 实验目的
1、 理解贪心算法的概念,掌握贪心算法的基本要素。
2、 掌握设计贪心算法的一般步骤,针对具体问题,能应用贪心算法求解。
二、 实验内容
1、问题描述
活动安排问题
设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si
2、数据输入:文件输入或键盘输入。
3、要求:
1)完成上述两个问题中1个或全部,时间为 1 次课。
2)独立完成实验及实验报告。
三、 实验步骤
1、 理解方法思想和问题要求。
2、 采用编程语言实现题目要求。
3、 上机输入和调试自己所写的程序。
4、附程序主要代码:2、活动规划问题
#include
#include
#include
using namespace std;
struct node
{
int start;
int end;
} a[11111];
bool cmp(node x,node y)
{
if(x.end
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
sort(a,a+n,cmp);
ans=0;
end=-1e9-100;
for(i=0;i
if(a[i].start>=end) {
ans++;
end=a[i].end;
}
}
cout<
return 0;
}
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), 从而最优解和我们贪心得到的解多了一个相同的,经过一个一个替换,我们可以把最优解完全替换成我们贪心策略得到的解。 从而证明了这个贪心策略的最优性。
本文来源:https://www.2haoxitong.net/k/doc/897fae6da200a6c30c22590102020740be1ecdd8.html
文档为doc格式