活動選擇問題：
設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下，：
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
s[i] |
1 |
3 |
0 |
5 |
3 |
5 |
6 |
8 |
8 |
2 |
12 |
|
f[i] |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
求最多一次性不重復安排幾次活動（s[i]表示活動起始時間，f[i]表示結束時間）
/***********************************
* 貪心算法之活動選擇問題
* yanzh 2011-6-24
************************************/
#include <iostream>
using namespace std;
#define SET 1
#define UNSET 0
#define COUNT 12
typedef struct Activity{
int start; //活動起始時間
int end; //活動終止時間
int set; //活動是否被安排，0不安排, 1安排
Activity& operator=(const Activity &act)
{
if (this != &act)
{
this->start = act.start;
this->end = act.end;
this->set = act.set;
}
return *this;
}
}ACT;
//帶安排的活動，按照結束時間遞增順序已經排好序（算法導論16.1章）
//結果有兩個最大集合，下標分別為：{1,4,8,11}和{2,4,9,11}
//act[0]占位用，不具有實際意義
ACT act[COUNT] = { {0,0,0}, {1,4,0}, {3,5,0}, {0,6,0}, {5,7,0}, {3,8,0}, {5,9,0},
{6,10,0}, {8,11,0}, {8,12,0}, {2,13,0}, {12,14,0} };
void output_result()
{
int total = 0;
for (int i = 0; i < COUNT; i++)
{
if (act[i].set == SET)
{
cout<<"第 "<<i<<" 個活動被安排"<<endl;
total++;
}
}
cout<<"總計有 "<<total<<" 個活動被安排"<<endl;
}
//遞歸求
//參數： i,j表示帶處理的子問題S(i,j)
void recursion_activity(int i, int j)
{
int m = i + 1;
//找到S(i,j)中的第一個活動
while (m < j && act[m].start < act[i].end)
{
m = m + 1;
}
if (m < j)
{
act[m].set = SET;
return recursion_activity(m, j);
}
}
//迭代求
void iteration_activity()
{
int i = 0;
for (int m = 1; m < COUNT; m++)
{
if (act[m].start >= act[i].end)
{
act[m].set = SET;
i = m;
}
}
}
/*******************************************************************************
* 定理16.1
* 對于任意非空子問題S(i,j), 設a(m)是S(i,j)中具有最早結束時間的活動：那么,
* 1)活動a(m)在S(i,j)的某最大兼容活動子集中被使用；
* 2)子問題s(i,m)為空，所以選擇a(m)將使子問題S(m,j)為唯一可能非空的子問題。
*******************************************************************************/
int main(int argc, char *argv[])
{
//有參數用遞歸，否則用迭代
if (argc > 1)
recursion_activity(0, COUNT);
else
iteration_activity();
output_result();
return 0;
}