给定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;
}

运行结果

运行结果