給定n個(gè)活動(dòng)墩瞳，其中的每個(gè)活動(dòng)ai包含一個(gè)起始時(shí)間si與結(jié)束時(shí)間fi驼壶。設(shè)計(jì)與實(shí)現(xiàn)算法從n個(gè)活動(dòng)中找出一個(gè)最大的相互兼容的活動(dòng)子集S。
要求：分別設(shè)計(jì)動(dòng)態(tài)規(guī)劃與貪心算法求解該問(wèn)題喉酌。其中热凹，對(duì)貪心算法分別給出遞歸與迭代兩個(gè)版本的實(shí)現(xiàn)。

思路

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃的思路則對(duì)此問(wèn)題來(lái)說(shuō)較為復(fù)雜泪电，定義S_ij為在i任務(wù)結(jié)束之后般妙，j任務(wù)開(kāi)始之間所包含的任務(wù)的子集。定義兩個(gè)虛擬任務(wù)a_i相速、a_n+1碟渺，則問(wèn)題對(duì)應(yīng)了S_0,,n+1的解。S_ij的元素?cái)?shù)量則對(duì)應(yīng)了任務(wù)的數(shù)量和蚪。通過(guò)遞歸方程可知復(fù)雜度為O(n³)止状，可通過(guò)設(shè)定另一個(gè)二維數(shù)組以輸出元素。

遞歸方程

貪心算法

貪心算法的思路很簡(jiǎn)單攒霹，非空子集S_ij怯疤，若a_m結(jié)束的時(shí)間最早，則有：
貪心準(zhǔn)則：a_m一定屬于S_ij的某個(gè)最優(yōu)解且S_im為空催束。
貪心準(zhǔn)則的證明:
A_ijj為S_ij最優(yōu)解集峦，另其中的任務(wù)按照結(jié)束時(shí)間遞增排序,令a_k是A_ij的第一個(gè)結(jié)束的任務(wù),如果a_k=a_m,則證明成立。否則我們將a_k用a_m替換，則它成為了另一個(gè)解A'_ij塔淤，同樣是最優(yōu)解摘昌。
所以即將任務(wù)以結(jié)束時(shí)間遞增排序，第一個(gè)結(jié)束的任務(wù)一定在最優(yōu)解中高蜂，依次找出子問(wèn)題中最先結(jié)束聪黎，且開(kāi)始時(shí)間在前一個(gè)解最后一個(gè)任務(wù)結(jié)束之間之后。復(fù)雜度為O(n)备恤。同時(shí)很容易得出有遞歸和遞推兩種形式稿饰，一般采用遞推。

貪心算法

遞歸

遞推

#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;
}

運(yùn)行結(jié)果

運(yùn)行結(jié)果