文档介绍：素州矣通大学
《算法设计与分析》
实验报告4
题目 04-贪心算法
专业 计算机科学与技术
班级 计算机科学与技术1602班
学 号 201610333
姓名 石博洋
第4章贪心算法
实验题目与环境
用贪心算法解决活动安排问题。
设有n个活动的集合E={1,2, •••,!!},其中每个活动都要求使用同一资源，而在同 一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时 间si和一个结束时间fi,且si <fi o如果选择了活动i,则它在半开时间区间［si, fi)内占用 资源。若区间［si, fi)与区间［sj,切不相交，则称活动i与活动j是相容的。也就是说，当 siNg或sj>fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出 最大的相容活动子集合。
用贪心算法解决多机调度问题。
设有n个独立的作业(1, 2, •••,!!},由m台相同的机器(Ml, M2,…，Mm}进行加工 处理，作业i所需的处理时间为ti(lWiWn),每个作业均可在任何一台机器上加工处 理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业 在尽可能短的时间内由m台机器加工处理完成。
：
CPU： Intel(R) Core(TM) i3-2120 3. 3GHZ
内存：12GB
操作系统：Windows 7. 1 X64
编译环境： Mircosoft Visual C++ 6
问题分析
分析。
将活动按照结束时间进行从小到大排序。然后用i代表第i个活动，s［i］代表第i 个活动开始时间，f［i］代表第i个活动的结束时间。按照从小到大排序，挑选出结束时 间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找 出这些活动就是最大的相容活动子集合。事实上系统一次检查活动i是否与当前已选择 的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i,而继 续下一活动与集合A中活动的相容性。若活动i与之相容，则i成为最近加入集合A的 活动，并取代活动j的位置。
分析。
本问题是NP问题，因为任何作业都可以调度到任何机器。
采用最长处理时间作业优先的贪心选择策略可以设计出较好的近似算法。
(1)代码
#include ""
#include <iostream>
using namespace std;
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[]);
const int N = 11;
int main()
(
〃下标从1开始，存储活动开始时间
int s[] = ( 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 );
〃下标从1开始，存储活动结束时间
int f[] = ( 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
bool A[N + 1];
cout « "各活动的开始时间，结束时间分别为："<< endl;
for (int i = 1; i <