算法导论--学习笔记014

1.

贪心算法—活动选择问题

问题描述：设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi]内占用资源。若区间[si, fi]与区间[sj, fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动选择问题就是选择一个由相容活动构成的最大集合。

分析：所有可能共有2^n种，为了提高效率，考虑最优子结构

最优子结构

定义集合S[i,j]={a[k]∈S：f[i]≤s[k]<f[k]≤s[j]}，即S[i,j]是所有与a[i]和a[j]相容的活动的集合。为了表示整个活动，假设两个活动a[0]和a[n+1]，并定义f[0]=0,s[n+1]=∞。于是S=S[0,n+1]。

假设各种活动的结束时间单调递增排列，即：f[0]≤f[1]≤f[2]≤...≤f[n]≤f[n+1]

这样根据S[i,j]的定义，只要i≥j,则S[i,j]=∅。于是子问题是在S[0,n+1]中选择最大的相容活动子集。我们假设S[i,j]的一个解包含活动a[k],即f[i]≤s[k]<f[k]≤s[j]，利用a[k]产生两个子问题S[i,k]和S[k+1,j]

设c[i,j]为S[i,j]最大相容活动子集的个数，那么

       0                     S[i,j]=∅

c[i,j]=max{c[i,k]+c[k+1]+1}   i<k<jS[i,j]≠∅

基于上式可写出一个动态规划的算法，这个算法的复杂度是O(n^3)（三个循环）

这个问题还有另外一个特征，从c[i,j]=max{c[i,k]+c[k+1]+1}   i<k<j可见，为了计算c[i,j],k要从i+1到j-1循环，其次解决两个子问题c[i,k]和c[k+1,j],假如一步就能确定k的值并且减少计算一个子问题，算法效率就能大大提高。确实可以这样做，因为“贪婪选择性”

贪婪选择性

S[i,j]为非空子问题，设a[m]是S[i,j]中最早完成的一个活动，f[m]=min{f[k]:a[k]∈S[i,j]}

 (1)活动a[m]包含在S[i,j]的一个（可能有多个）最大相容活动的子集中

（2）子问题S[i,m]是空集，a[m]使S[m,j]成为仅有的非空子问题

这样我们“贪婪地”选择S[i,j]中最早结束的活动

 

伪代码(假设所有活动的结束时间都已经单调递增排列）

select_activity(S,f,i,j)

m←i+1

whilem<j ands[m]<f[i]

   do x[m]←0

    m←m+1

ifm<j

  then x[m]←1

select_activity(S,f,m,j)

显然只需要扫描一遍，算法的运行时间为O(n).

代码：

#include<stdio.h>
#include<limits.h>
#include<string.h>
void select(int s[],int f[],int i,int j,int x[])
{
 int m=i+1;
 while(m<j&&s[m]<f[i])
 {
  x[m]=0;
  m++;
 }
 if(m<j)
 {
  x[m]=1;
  select(s,f,m,j,x);
 }
}
int main()
{
 int s[13]={0,1,3,0,5,3,5,6,8,8,2,12,0};
 intf[13]={0,4,5,6,7,8,9,10,11,12,13,14,INT_MAX};
 int x[13];
 select(s,f,0,12,x);
 int i,sum=0;
 for(i=1;i<12;i++)
 {
  printf("%d",x[i]);
  sum=sum+x[i];
 }