动态规划总是在追求全局最优的解，但是有时候，这样有点费时。贪心算法，在求解过程中，并不追求全局最优解，而是追求每一步的最优，所以贪心算法也不保证一定能够获得全局最优解，但是贪心算法在很多问题却额可以求得最优解。

 一、问题概述

        活动选择问题：

        假定一个有n个活动(activity)的集合S={a1,a2,....,an}，这些活动使用同一个资源（例如同一个阶梯教室），而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi，其中0<=si<fi<正无穷。如果被选中国，任务ai发生在半开时间区间[si,fi)期间。如果两个活动ai和aj满足[si,fi)和[sj,fj)不重叠，则称它们是兼容的。也就说，若si>=fj或sj>=fi，则ai和aj是兼容的。在活动选择问题中，我们希望选出一个最大兼容活动集。假定活动已按结束时间fi的单调递增顺序排序：

                                                                                        f1<=f2<=f3<=f4<=...<=fn-1<=fn

        例如，考虑下面的活动集合：

        可以看到，{a3,a9,a11}是由相互兼容的活动组成。但它不是一个最大集，{a1,a4,a8,a11}更大，是一个最大集，最大集可以有多个不同的。

        假设：Sij表示在ai结束之后，在aj开始之前的活动的集合。Aij表示Sij的一个最大相互兼容的活动子集。那么只要Sij非空，则Aij至少会包含一个活动，假设为ak。那么可以将Aij分解为：Aij = Aik+ak+Akj。假设Cij为Aij的大小，那么有Cij=cik+ckj+1。

        但是我们并不知道具体是k等于多少的时候，可以让ak一定位于Aij中，所以我们采用动态规划的方式，遍历所有可能的k值，来取得。于是有：

        接下来，如果按照动态规划的方式，就可以采用自底向上的递归来求解最优的解。

二、贪心算法

        但是贪心算法却要简单许多，贪心算法直接在每一步选择当前看来最好的选择。比如在一开始的时候，我们要选择在Aij中的第一个活动，我们选择活动结束时间最早的那个活动，这样能够给其他活动尽可能的腾出多余的时间。而后每一步都在剩下的活动中选取，也遵循类似的原则。由于获取已经按照fi排序好，所以这里第一个选择的活动就是a1。但是问题来了，我们能否确定a1一定在Aij中呢，在这个问题中，答案是肯定的，可以给出简单的证明：

        假设Aij是Sij的某个最大兼容活动集，假设Aij中，最早结束的活动是an，分两种情况：

        ①如果an=a1，则得证

        ②如果an不等于a1，则an的结束时间一定会晚于a1的结束时间，我们用a1去替换Aij中的an，于是得到A`，由于a1比an结束的早，而Aij中的其他活动都比an的结束时间开始 的要晚，所以A`中的其他活动 都与a1不想交，所以A`中的所有活动是兼容的，所以A`也是Sij的一个最大兼容活动集。

        于是证明了命题。

根据上面的结论，我们可以给出贪心算法在解决这个问题的两种方式：递归和迭代方式，两种算法都是按照自顶向下来求解问题的。

递归方式：

/*
 * 递归版本
 */
void Recursive_Activity_Selector(vector<int>* A, int* s, int* f, int k, int n) {

	int m = k + 1;
	while (m <= n && s[m] < f[k]) {
		m++;
	}

	if (m <= n) {
		A->push_back(m);
		Recursive_Activity_Selector(A, s, f, m, n);
	}
}

迭代方式：

/*
 * 迭代版本
 */
vector<int>* Greedy_Activity_Selector(int*s, int*f, int n) {
	vector<int>* A = new vector<int>;

	int k = 1;
	A->push_back(k);

	for (int m = 2; m <= n; m++) {
		if (s[m] >= f[k]) {
			A->push_back(m);
			k = m;
		}
	}

	return A;
}

三、算法复杂度分析：

        假设实现活动已经按照fi的升序排列好了的话，会发现实际上贪心算法在处理这个问题的时候只做了一次遍历，所以算法复杂度为O(n)。

完整代码：

/*
 * 活动选择问题：
 *
 * 调度竞争共享资源的多个活动的问题，目标是选出一个最大的互相兼容的活动集合。假定有一个n个活动的集合S={a1,a2,a3...,an}，
 * 这些活动使用同一个资源（例如同一个阶梯教室），而这个资源在某个时刻只能供一个活动使用。每个互动ai都有一个开始时间s和一个结束时间fi，
 * 其中)<=si<fi<无穷。如果被选中，任务ai发生在半开时间区[si,fi)期间。如果两个活动ai和aj满足[si,fi)和[sj,fj)不重叠，则称它们是兼容的。
 * 也就是说，若si>=fj，或sj>=fi，则ai和j是兼容的。在活动选择问题中，我们希望选出一个最大兼容活动集。假定活动已按照结束时间的单调递增
 * 排序
 *
 * 原本的思路：按照动态规划的方法来求，先求子问题：将Sij的一个最大兼容活动集合设为Aij，于是Aij至少包含一个活动ak，则：
 * 可以将Aij划分为子问题：Aij=Aik+ak+Akj
 *
 * 但是我们一开始不能知道哪一个k能够使得ak一定在最大兼容活动集Aij中，于是一般的需要从i~j便利所有的k的可能取值，来找这个ak。
 *
 * 上面是动态规划的思路；但是对于贪心算法而言，这里ak不去 遍历，而只是去寻找第一个结束的活动，也就是a1。这里可以证明，a1一定是在
 * Sij的某一个最大兼容活动集Aij中。证明方法：
 *
 * 假设Aij是Sij的某个最大兼容活动集，假设Aij中，最早结束的活动是an，分两种情况：
 *
 * ①如果an=a1，则得证
 * ②如果an不等于a1，则an的结束时间一定会晚于a1的结束时间，我们用a1去替换Aij中的an，于是得到A`，由于a1比an结束的早，而Aij中的其他活动
 * 都比an的结束时间开始 的要晚，所以A`中的其他活动 都与a1不想交，所以A`中的所有活动是兼容的，所以A`也是Sij的一个最大兼容活动集。
 *
 * 得证
 *
 * 于是我们下面使用贪心算法来做，分别用递归和迭代两个版本。
 *
 */

#include <iostream>
#include <vector>

using namespace std;

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int Adjust_Arr(int* a, int* b, int start, int end) {

	int p = start;
	int q = end;
	int i = p - 1;
	int j = p;

	int key = a[q];

	while (j < q) {
		if (a[j] >= key) {
			j++;
			continue;
		} else {
			i++;
			swap(a + i, a + j);
			swap(b + i, b + j);
			j++;
		}
	}

	i++;
	swap(a + i, a + q);
	swap(b + i, b + q);
	return i;
}

void Quick_Sort(int* a, int* b, int start, int end) {
	if (start < end) {
		int mid = Adjust_Arr(a, b, start, end);
		Quick_Sort(a, b, start, mid - 1);
		Quick_Sort(a, b, mid + 1, end);
	}
}

void Print_Arr(int* a, int len) {
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << endl;
}

/*
 * 递归版本
 */
void Recursive_Activity_Selector(vector<int>* A, int* s, int* f, int k, int n) {

	int m = k + 1;
	while (m <= n && s[m] < f[k]) {
		m++;
	}

	if (m <= n) {
		A->push_back(m);
		Recursive_Activity_Selector(A, s, f, m, n);
	}
}

/*
 * 迭代版本
 */
vector<int>* Greedy_Activity_Selector(int*s, int*f, int n) {
	vector<int>* A = new vector<int>;

	int k = 1;
	A->push_back(k);

	for (int m = 2; m <= n; m++) {
		if (s[m] >= f[k]) {
			A->push_back(m);
			k = m;
		}
	}

	return A;
}

int main() {

	int s[12] = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 };

	int f[12] = { 0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16 };

	//先将f按从小到大排序，s的位置随f而动
	Quick_Sort(f, s, 0, 12 - 1);

//	vector<int>* A = new vector<int>;
//	Recursive_Activity_Selector(A, s, f, 0, 12 - 1); //这里实际上下标只能取到11

	vector<int>* A = Greedy_Activity_Selector(s, f, 12 - 1);

	cout << "===========" << endl;
	vector<int>::iterator iter;

	for (iter = A->begin(); iter != A->end(); iter++) {
		cout << *iter << ' ';
	}
	cout << endl << "===========" << endl;

	delete A;

	return 0;
}

【算法导论】贪心算法之活动选择问题