实验九：活动安排问题（贪心算法）报告
2017061111 李静娴
1．问题描述
设有
n
个活动的集合
E={1,2,
…
,n}
，其中每个活动都要求使用同一资源，如演讲会场等，
而在同一时间内只有一个活动能使用这一资源。每个活动
i
都有一个要求使用该资源的起
始时间
si
和一个结束时间
,
且
si <
。如果选择了活动
i
，则它在半开时间区间
[si, )
内占用
资源。若区间
[si, )
与区间
[sj, )
不相交
,
则称活动
i
与活动
j
是相容的。也就是说，当
si
≥
或
sj
≥
时，活动
i
与活动
j
相容。活动安排问题就是要在所给的活动集合中选出最大的相容活
动子集合。
2．实验目的
（1）熟悉贪心算法，并学以致用
（2）熟练掌握活动安排问题算法
3．实验原理
将活动按照结束时间进行从小到大排序。然后用
i
代表第
i
个活动，
s[i]
代表第
i
个活动开始
时间，
f[i]
代表第
i
个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，
并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大
的相容活动子集合。事实上系统一次检查活动
i
是否与当前已选择的所有活动相容。若相
容活动
i
加入已选择活动的集合中，否则，不选择活动
i
，而继续下一活动与集合
A
中活动
的相容性。若活动
i
与之相容，则
i
成为最近加入集合
A
的活动，并取代活动
j
的位置。
算法时间复杂度分析：O(n^2)。
4．实验设计
（1）
输入数据格式：输入活动的个数，要求都为整型的数，范为 1-15
生成方式：在输入数据规模之后，程序中先生成基于当前时间的随机数种子，然后通过 for
循环语句，每次用随机函数生成一个范围在 0-20 的随机数并将其放入活动开始时间数组 s[]
和活动结束时间数组 f[]中。
数据规模：用户手动输入数据规模。
（2）
该程序先是基于当前系统时间生成随机数种子，再根据输入的数据规模创建两个相应
大小的整型数组，然后通过 for 循环语句和随机函数 rand()循环生成数据规模个数的元素并
存入创建的数组中。然后调用 greedySelector(n,s,f,a)函数，同时，greedySelector(n,s,f,a)函数
里的变量 count，用于输出最优值，即安排的活动的个数， a[]数组，记录了每个活动的
Bool 值，用于输出最优解，即输出活动安排的序列。
（3）
程序运行的结果有 3 个，先是打印活动即活动起止时间，然后最优值，即安排的活动
的个数，再输出最优解，即输出活动安排的序列。
5．实验结果与分析
qq_42236488
- 粉丝: 4
- 资源: 17
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0