贪心算法概念.cpp

算法分析中的贪心算法的实现

/*
贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优
加以考虑，它所作出的选择只是在某种意义上的局部最优选择。
*/
/*
活动安排问题：
设有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相容。活动安排问题就是要在所给的活动集合中选出最大
的相容活动子集合。
*/
/*
下面是解此问题的贪心算法：
各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序：
f1<=f2<=...<=fn。如果所给出的活动未按此排列，我们可以用O(nlongn)的时间将
它排序。
*/

template<class Type>
void GreedySelector( int n, Type s[], Type f[], bool A[] )
{
	A[1] = true;
	int j = 1;
	for( int i = 2; i <= n; ++i )
	{
		if ( s[i] >= f[j] )
		{
			A[i] = true;
			j = i;
		}
		else
		{
			A[i] = false;
		}
	}
}

/*
该算法用集合A来存储所选择的活动。活动i在集合A中，当且仅当A[i]为true。
变量j用以记录最近一次加入到A中的活动
*/