贪心算法解决活动安排问题

青旅半醒 2022-06-07 04:35 303阅读 0赞

**4.2 活动安排问题**  
设有n个活动的集合E=\{1, 2, …, n\}，其中每个活动都要 求使用同一资源，如演讲会场等，而在同一时间内只有一个 活动能使用这一资源。 每个活动i都有一个要求使用该资源的起始时间si和一个 结束时间fi，且si＜fi。如果选择了活动i，则它在半开时间区 间\[si, fi)内占用资源。若区间\[si, fi)与区间\[sj, fj)不相交，则 称活动i与活动j是相容的。当si≥fj或sj≥fi时，活动i与活动j相 容。 活动安排问题就是在所给的活动集合中选出最大的相容 活动子集合。  
输入： 测试数据的第一行是正整数n （n≤100），表示活动数，后跟n 行，每行的三个数分别表示活动的 编号、开始时间、结束时间，数据 之间由一个空格分隔开。 输出： 输出选中的活动编号（或选中 的活动个数）。  
输入样例：  
11  
1 1 4  
2 3 5  
3 0 6  
4 5 7  
5 3 8  
6 5 9  
7 6 10  
8 8 11  
9 8 12  
10 2 13  
11 12 14  
输出样例：  
1 4 8 11  
代码实现：

//ACM贪心算法——活动安排问题
    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct ActionInfo {					//单个活动的信息节点
    	int index;						//活动编号
    	int startTime;					//活动开始时间
    	int endTime;					//活动结束时间
    };
    bool cmp(const ActionInfo &a, ActionInfo &b);
    int main()
    {
    	int actionsGroups = 0;							//所有的活动的组数
    	cin >> actionsGroups;
    	ActionInfo *act = new ActionInfo[actionsGroups];//开辟活动数组
    	for (int i = 0; i < actionsGroups; i ++) {
    		//输入所有活动的信息
    		cin >> act[i].index >> act[i].startTime 
    			>> act[i].endTime;
    	}
    	//对所有活动按照endtime升序排序
    	sort(act, act + actionsGroups, cmp);
    	//贪心算法：只要下一个活动的开始时间在当前活动结束时间之后则这两个活动相容
    	//把此活动加入符合条件的集合
    	int currentAction = 0, count = 0;				//当前符合要求的活动
    	int notConflictActionsIndex[100];				//此处用一个常量来定义
    	notConflictActionsIndex[count] = act[0].index;
    	for (int j = 1; j < actionsGroups; j ++) {
    		if (act[j].startTime >= act[currentAction].endTime) {
    			currentAction = j;
    			notConflictActionsIndex[++count] = act[j].index;	//记下不冲突活动的编码
    		}
    	}
    	//输出
    	for (int k = 0; k <= count; k ++) {
    		cout << notConflictActionsIndex[k] << ' ';
    	}
    	delete[] act;									//释放资源
    	system("pause");
    	return 0;
    }
    bool cmp(const ActionInfo &a, ActionInfo &b) {
    	//比较函数，作为sort的第三个参数，实现升序排序
    	if (a.endTime <= b.endTime) {
    		return true;
    	}
    	return false;
    }

总结：  
1数据结构：  
struct action \{  
int index; //活动的编号  
int f; //结束时间  
\};  
2排序：按活动的结束时间升序排序 排序比较因子：  
if (a.f<=b.f) return true;  
return false; \} 使用标准模板库函数排序： sort(a, a+n, cmp);  
此处推荐一片具体介绍C++ sort函数的文章：  
[STL sort 函数内部的实现 为什么会比你写的快][STL sort _]  
3 贪心选择：优先选择结束时间早的  
4 活动安排问题就是要在所给的活动集合中选出最大 的相容活动子集合，是可以用贪心算法有效求解的很好 例子。 该问题要求高效地安排一系列争用某一公共资源的 活动。 贪心算法提供了一个简单、漂亮的方法使得尽可能 多的活动能兼容地使用公共资源。  
**4.3 贪心算法**  
***贪心算法\*\*\*是一种在每一步选择中都采取在当前状态 下最好或最优的选择，希望得到结果是最好或最优的算法。 贪心算法是一种能够得到某种度量意义下的最优解的 分级处理方法，通过一系列的选择得到一个问题的解，而 它所做的每一次选择都是当前状态下某种意义的最好选择。 即希望通过问题的局部最优解求出整个问题的最优解。 这种策略是一种很简洁的方法，对许多问题它能产生 整体最优解，但不能保证总是有效，因为它不是对所有问 题都能得到整体最优解。 利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解； （2）如何选择贪心标准，以得到问题的最优/较优解。  
\*\*\*贪心选择性质***： 贪心选择性质是指所求问题的整体最优解可以通过一 系列局部最优的选择，即贪心选择来达到。 这是贪心算法可行的第一个基本要素，也是贪心算法 与动态规划算法的主要区别。 （1）在动态规划算法中，每步所做的选择往往依赖 于相关子问题的解，因而只有在解出相关子问题后，才能 做出选择。 （2）在贪心算法中，仅在当前状态下做出最好选择， 即局部最优选择，然后再去解出这个选择后产生的相应的 子问题。  
***最优子结构***： (1) 当一个问题的最优解包含其子问题的最优解时，称此 问题具有最优子结构性质。 运用贪心策略在每一次转化时都取得了最优解。问题的最 优子结构性质是该问题可用贪心算法或动态规划算法求解 的关键特征。 (2) 贪心算法的每一次操作都对结果产生直接影响，而动 态规划则不是。 贪心算法对每个子问题的解决方案都做出选择，不能回退； 动态规划则会根据以前的选择结果对当前进行选择，有回 退功能。 动态规划主要运用于二维或三维问题，而贪心一般是一维 问题。  
***使用贪心算法求解问题应该考虑如下几个方面***： （1）候选集合A：为了构造问题的解决方案，有一个候 选集合A作为问题的可能解，即问题的最终解均取自于 候选集合A。 （2）解集合S：随着贪心选择的进行，解集合S不断扩展， 直到构成满足问题的完整解。 （3）解决函数solution：检查解集合S是否构成问题的 完整解。 （4）选择函数select：即贪心策略，这是贪心法的关键， 它指出哪个候选对象最有希望构成问题的解，选择函数 通常和目标函数有关。 （5）可行函数feasible：检查解集合中加入一个候选对 象是否可行，即解集合扩展后是否满足约束条件  
以上主要通过老师对贪心算法概念的讲解及活动安排的主要解决步骤和贪心策略，对活动安排的代码进行了实现。

![公众号：Dawo][Dawo]

[STL sort _]: http://blog.sina.com.cn/s/blog_9d987af501014zlj.html
[Dawo]: /images/20220607/b828efcc71fe46108dc6eb9f6bdc1bf1.png