一、问题描述 有一个n个活动的集合S={a1, a2, … , an}，这些活动使用同一个资源，而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi，其中0≤si＜fi＜∞。如果被选中，任务ai占据半开区间时间 [si, fi)。如果两个活动[)和[)不重叠，则称它们是兼容的。该问题就是要找出最大兼容子集。例如下表所示的活动集合S，其中各项活动按照结束时间的单调递增顺序排序：
二、动态规划解决过程 (1)活动选择问题的最优子结构 定义Sij是S的子集，其中每个活动都是在ai结束之后开始，且在aj开始之前结束。Sij={ak∈S: fi≤sk≤fk≤sj} （当i≥j时，Sij为空集） 最优子结构为：假设Sij的最优解Aij包含活动ak，则对Sik的解Aik和Skj的解Akj必定是最优的。 通过一个活动ak将问题分成两个子问题，下面的公式可以计算出Sij的解Aij。 Aij=Aik∪{ak}∪Akj (2)一个递归解： 设c[i][j]为Sij中最大兼容子集中的活动数目，当Sij为空集时，c[i][j]=0；当Sij非空时，若ak在Sij的最大兼容子集中被使用，则子问题Sik和Skj的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。 c[i][j]的完整计算公式如下：
(3)C语言实现
/* 动态规划求解过程：采用自底向下的策略进行计算c[i][j]，引入复杂数组ret[n][n]保存中间划分的k值 设c[i][j]为Sij中最大兼容子集中的活动数目，当Sij为空集时，c[i][j]=0； 当Sij非空时，若ak在Sij的最大兼容子集中被使用，则子问题Sik和Skj的最大兼容子集也被使用， 故可得到c[i][j] = c[i][k]+c[k][j]+1。 */ void dynamic_activity_selector(int *s, int *f, int num, int **c, int **ret) { int i, j, k, q; //当i>=j时，子问题的解为空集 for (i = 1; i <= num; i++) { for (j = i; j <= num; j++) c[i][j] = 0; } //当i<j时，需要寻找子问题的最优解，寻找k值把原问题分割两个子问题 for (j = 2; j <= num; j++) { for (i = 1; i < j ; i++) { for (k = i + 1; k < j; k++) { if (s[k] >= f[i] && f[k] <= s[j]) //判断k活动是否满足兼容性 { q = c[i][k] + c[k][j] + 1; if (c[i][j] < q) { c[i][j] = q; ret[i][j] = k; } } } } } }三、贪心算法解决过程 针对活动选择问题，认真分析可以得出以下定理：对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动，那么： (1)活动am在Sij中的某最大兼容活动子集中被使用。 (2)子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题。 有这个定理，就简化了问题，使得最优解中只使用一个子问题，在解决子问题Sij时，在Sij中选择最早结束时间的那个活动。 贪心算法自顶向下地解决每个问题，解决子问题Sij，先找到Sij中最早结束的活动am，然后将am添加到最优解活动集合中，再来解决子问题Smj。 基于这种思想可以采用递归和迭代进行实现。 递归实现过程如下所示：
void recursive_activity_selector(int *s, int* f, int k, int n, int *set) { int m = k + 1; int *pset = set; while (m <= n && s[m] < f[k]) //查找Sk中最早结束的活动，直到找到第一个与ak兼容的活动am， m += 1; //此活动满足sm>=fk if (m <= n) { *pset++ = m; //添加到结果集中 recursive_activity_selector(s, f, m, n, pset); } }迭代实现过程如下：
/* 迭代贪心算法 */ void greedy_activity_selector(int *s, int *f, int num, int *set) { *set++ = 1; int k = 1; for (int m = 2; m <= num; m++) { if (s[m] >= f[k]) { *set++ = m; k = m; } } }测试代码如下：
int main() { int s[LENGTH] = { -1, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 }; int f[LENGTH] = { -1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }; int set[LENGTH] = { 0 }; for (int i = 0; i < LENGTH; i++) { set[i] = 0; } greedy_activity_selector(s, f, LENGTH - 1, set); for (int i = 0; i < LENGTH; i++) { if (set[i] != 0) printf("a%d ", set[i]); } printf("\n"); return 0; }测试结果如下：
四、总结 四、总结 活动选择问题分别采用动态规划和贪心算法进行分析并实现。动态规划的运行时间为O(n^3)，贪心算法的运行时间为O(n)。动态规划解决问题时全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。贪心算法的主要思想就是对问题求解时，总是做出在当前看来是最好的选择，产生一个局部最优解。
