给定 n 个活动, 其中的每个活动 ai 包含一个起始时间 si 与结束时间 fi. 设计与实现算法从 n 个活动中找出一个最大的相互兼容的活动子集 S.
要求: 分别设计动态规划与贪心算法求解该问题. 其中, 对贪心算法分别给出递归与迭代两个版本的实现.
思路
动态规划
动态规划的思路则对此问题来说较为复杂, 定义 Sij 为在 i 任务结束之后, j 任务开始之间所包含的任务的子集. 定义两个虚拟任务 ai,an+1, 则问题对应了 S0,,n+1 的解. Sij 的元素数量则对应了任务的数量. 通过递归方程可知复杂度为 O(n3), 可通过设定另一个二维数组以输出元素.
递归方程
贪心算法
贪心算法的思路很简单, 非空子集 Sij, 若 am 结束的时间最早, 则有:
贪心准则: am 一定属于 Sij 的某个最优解且 Sim 为空.
贪心准则的证明:
Aijj 为 Sij 最优解, 另其中的任务按照结束时间递增排序, 令 ak 是 Aij 的第一个结束的任务, 如果 ak=am, 则证明成立. 否则我们将 ak 用 am 替换, 则它成为了另一个解 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;
- }
运行结果
运行结果
来源: http://www.jianshu.com/p/dbfc912af47c