(C/C++)区间调度问题的解决及输出:动态规划、贪心算法(递归、递推)

给定n个活动，其中的每个活动ai包含一个起始时间si与结束时间fi。设计与实现算法从n个活动中找出一个最大的相互兼容的活动子集S。
要求：分别设计动态规划与贪心算法求解该问题。其中，对贪心算法分别给出递归与迭代两个版本的实现。

思路

动态规划

动态规划的思路则对此问题来说较为复杂，定义S_ij为在i任务结束之后，j任务开始之间所包含的任务的子集。定义两个虚拟任务a_i、a_n+1，则问题对应了S_0,n+1的解。S_ij的元素数量则对应了任务的数量。通过递归方程可知复杂度为O(n³)，可通过设定另一个二维数组以输出元素。

贪心算法

贪心算法的思路很简单，非空子集S_ij，若a_m结束的时间最早，则有：
贪心准则：a_m一定属于S_ij的某个最优解且S_im为空。
贪心准则的证明:
A_ijj为S_ij最优解，另其中的任务按照结束时间递增排序,令a_k是A_ij的第一个结束的任务,如果a_k=a_m,则证明成立。否则我们将a_k用a_m替换，则它成为了另一个解A’_ij，同样是最优解。
所以即将任务以结束时间递增排序，第一个结束的任务一定在最优解中，依次找出子问题中最先结束，且开始时间在前一个解最后一个任务结束之间之后。复杂度为O(n)。同时很容易得出有递归和递推两种形式，一般采用递推。

#include <iostream>
#include <vector>
#define TASK_COUNT 8
using namespace std;
int finish[TASK_COUNT + 2] = { -1,2,4,6,7,8,9,12,15,255};
int start[TASK_COUNT + 2] = { -1,1,2,3,3,1,7,10,13,255};
int _count[TASK_COUNT + 2][TASK_COUNT + 2];
int p[TASK_COUNT + 2][TASK_COUNT + 2];
void recursive(int* start,int* finish,int begin,int end) {
	int m = begin + 1;
	while (m <= end) {
		if (start[m] >= finish[begin]) {
			break;
		}
		m++;
	}
	if (m <= end) {
		cout << m << " ";
		recursive(start, finish, m, end);
	}
}

void iterative(int* start, int* finish) {
	int len = TASK_COUNT;
	int pre = 0;
	for (int i = 1; i <= len; i++) {
		if (start[i] >= finish[pre]) {
			cout << i << " ";
			pre = i;
		}
	}
}


void dp(int* start, int* finish) {
	for (int len = 2; len <= TASK_COUNT + 2; len++) {
		for (int begin = 0; begin <= TASK_COUNT + 1; begin++) {
			int end = begin + len - 1;
			int max = 0;
			int slice = 0;
			for (int k = begin + 1; k <= end - 1; k++) {
				if (start[k] >= finish[begin]&&finish[k]<=start[end]) {
					int temp = _count[begin][k] + _count[k][end] + 1;
					if (temp > max) {
						max = temp;
						slice = k;
					}
				}
			}
			p[begin][end] = slice;
			_count[begin][end] = max;
		}
	}
}

void printDp( int begin, int end) {
	int pos = p[begin][end];
	if (pos == 0)
		return;
	cout << pos << " ";
	printDp(begin, pos);
	printDp(pos, end);
	
}

int main(void) {
	for (int i = 0; i <= TASK_COUNT; i++) {
		cout << i << ":";
		for (int j = 0; j < start[i]; j++) {
			cout << "  ";
		}
		for (int j = start[i]; j < finish[i]; j++) {
			cout << "■";
		}
		cout << endl;
	}
	recursive(start, finish, 0, TASK_COUNT);
	cout << endl;
	iterative(start, finish);
	cout << endl;
	for (int i = 0; i <= TASK_COUNT + 2; i++) {
		for (int j = 0; j <= TASK_COUNT + 2; j++) {
			_count[i][j] = 0;
			p[i][j] = 0;
		}
	}
	dp(start, finish);
	cout << _count[0][TASK_COUNT + 1] << endl;
	printDp(0, TASK_COUNT + 1);
	system("pause");
	return 0;
}

运行结果