贪心算法的经典问题 -- 活动选择问题
2013-02-27 12:01:28 最后更新: 2015-08-06 23:42:12 访问数量：1920
问题描述
活动选择问题就是对几个相互竞争的活动进行调度，每个活动都要求独占某一资源，要在N个活动中挑选出一个互相兼容的活动的最大子集合
问题分析
我们可以首先按照各个活动的结束时间将活动进行排序，对于活动 ai 到 aj，如果兼容活动数不为0并且 ak 是其中的一个被兼容的活动，那么
- 活动的总数 = ai 到 ak 的兼容活动数 + ak 到 aj 的兼容活动数 + 1
这样，我们就可以将原问题划分为 ai 到 ak 的兼容活动数 与 ak 到 aj 的兼容活动数 两个子问题来分别计算，因此我们可以使用动态规划算法
但是，对于这个问题，我们可以从另外一个角度考虑，就是寻找 ai 到 ak 的最大兼容子集合的最早结束时间，这样对于aj（j>k），将有最大可能添加到原集合，因为活动是按照各个活动的结束时间递增排序的，因此，我们只要顺序地选择活动就可以得到当前子集的最早结束时间的活动，最终，可以得到全局最优解
算法代码
/*
* file: main.c
* author: 龙泉居士
* date: 2013-02-27 12:00
*/
#include <stdio.h>
#include "function/function.h"
int main ()
{
int s[11] = {5, 3, 8, 6, 2, 3, 1, 0, 5, 12, 8};
int f[11] = {7, 5, 11, 10, 13, 8, 4, 6, 9, 14, 12};
activity (s, f, 11);
return 1;
}
/*
* file: function.h
* author: 龙泉居士
* date: 2013-02-27 12:01
*/
#ifndef FUNCTION_H_20130227
#define FUNCTION_H_20130227
void activity (int *s, int *f, int size);
void sort_activity (int *s, int *f, int beg, int end);
void exch (int *s, int *f, int i, int j);
#endif
/*
* file: function.c
* author: 龙泉居士
* date: 2013-02-27 12:01
*/
#include <stdio.h>
#include "function.h"
void activity (int *s, int *f, int size)
{
sort_activity (s, f, 0, size-1);
int i, last_f = f[0], count=1;
printf ("activities:\n1 ");
for (i=1; i<size; ++i)
if (s[i]>=last_f)
{
last_f = f[i];
++count;
printf ("%d ", i+1);
}
printf ("\nThere are %d activities\n", count);
}
void sort_activity (int *s, int *f, int beg, int end)
{
if (beg >= end)
return;
int i=beg, j=beg+1;
while (1)
{
if (f[j]<f[beg])
{
++i;
exch(s, f, i, j);
}
++j;
if (j > end)
break;
}
exch (s, f, beg, i);
sort_activity(s, f, beg, i-1);
sort_activity(s, f, i+1, end);
}
void exch (int *s, int *f, int i, int j)
{
if (i == j)
return;
s[i] = s[i]^s[j];
s[j] = s[i]^s[j];
s[i] = s[i]^s[j];
f[i] = f[i]^f[j];
f[j] = f[i]^f[j];
f[i] = f[i]^f[j];
}
