1.活动选择问题

1.1.问题描述

​ 假定有n个活动组成的集合$S = { a_1,a_2,a_3,…,a_n }$，这些活动使用同一个资源且该资源同一时刻只能由一个活动使用。假设各活动使用资源的开始时间和结束时间用$s_i$和$f_i$表示($0 \leq s_i \lt f_i \lt \infin$)，并且如果两个活动各自的使用资源时间段$[s_i,f_i)$互不相交，那么则称两个活动兼容。

​ 活动选择(activity selection)问题需要找出最大兼容活动集合。

1.2.解决方法

1.2.1.动态规划

​ 定义$S_{ij}$表示在活动$a_i$结束后开始，在活动$a_j$开始前结束的活动的集合。动态规划法解决该问题的思路是这样的：

​ 1.寻找最优子结构。最优子结构体现为如果已知问题$S_{ij}$的最优解$A_{ij}$包含某个活动$a_k$，那么去掉该活动后，剩下的子问题就为$S_{ik}$和$S_{kj}$，此时这两个子问题的一定是最优解，否则$A_{ij}$不是最优解。

​ 2.递归定义代价。设$c[i,j]$为$S_{ij}$的最大兼容活动集合中活动数量，那么很容易知道其递归定义为：
\(c[i,j]=\begin{cases} 0 & S_{ij} = \empty \\ max_{a_k \in S_{ij}}(c[i,k]+c[k,j]+1) & S_{ij} \neq \empty \end{cases}\) 注意：上式中求最大值的条件$a_k \in S_{ij}$可以修改为$i \lt k \lt j$，如果已经按照结束时间升序对活动进行排序，并且具体算法实现需要判断$s_k$和$f_i$、$f_k$和$s_j$之间的关系，这是因为活动$a_k$的结束时间晚于$a_i$的结束时间、早于$a_j$的结束时间不能保证其开始时间晚于$a_i$的结束时间，其结束时间早于$a_j$的开始时间。但如果$i \notin (i,j)$，那么其必然不在$S_{ij}$内。即$i \lt k \lt j$是$a_k \in S_{ij}$的必要条件，但是编程实现会比判断$a_k \in S_{ij}$方便一些。{:.notice–info}

​ 3.实现算法并重构解，这里省略。

1.2.1.贪心算法

​ 活动选择的贪心算法的主要思想是：能否通过每次都选最早结束的活动，将剩下的时间尽可能多的留给其他活动，从而最终达到最优解呢？为了让上述方法可行，需要证明该问题具有贪心性质。

1.2.1.1.正确性证明

​ 我们需要证明：对于问题$S_{ij}$，其最优解一定包含最早结束的活动$a_m$。

​ 不妨设上述结论不成立，即最优解中不包含最早结束的活动$a_m$，任取最优解中最早结束活动$a_k$，那么可以构造一个新的集合$A^{,}{ij} = A{ij}-a_k \cup a_m$，新的集合与最优解的活动数量相同，并且由于$a_m$是最早结束的活动，故$f_m \leq f_k$，因此其必然与$A_{ij}$内其他活动兼容，故$A^{,}_{ij}$是一个新的最优解，其包含最早结束活动。我们总可以通过上述方法得到包含最早结束活动的最优解，即贪心选择总是最优解的一部分，也即“局部最优”一定是全局最优。

1.2.1.2.递归贪心算法

递归贪心算法只需找出当前集合中最先完成的、与已选活动兼容的活动即可，然后递归调用函数解决剩余集合组成的子问题。

1.2.1.3.迭代贪心算法

迭代贪心算法只需遍历已按完成时间升序排列好的活动序列，并贪心地将最早结束且兼容的活动加入集合。

1.2.1.4.算法时间复杂度

递归算法和迭代算法的复杂度均为$\Theta (n)$。

1.2.1.5.贪心算法的缺点

上述贪心算法一定可以得到一个最大兼容活动集合，但是不一定能得到时间利用率最高的最大兼容活动集合。