活动选择问题：
设待安排的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;
}