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