Activity Selector DP算法

#include <stdio.h>

#define MAX 1000
#define NUM 13
int DP_ActivitySelector(int i, int j, int s[], int f[], int A[][NUM])
{
	int k;
    int temp=0;
	int max=0;
	if(A[i][j] != -1) return A[i][j];

	if(i == j)    return max;
	else 
	{
		for(k = i+1; k < j; k++)
		{
			if(s[k] < f[i] || f[k] >s[j] ) return max;
			else
			{
				temp = DP_ActivitySelector(i, k, s, f, A) + DP_ActivitySelector(k, j, s, f, A) +1 ;

				if(temp > max) 
					max=temp;
				temp=0;
			}
		}
		A[i][j] = max;
		return max;		
	}
}

int main()
{
	int s[] = {0,1, 3, 0, 5, 3 ,5, 6, 8 ,8 ,2 ,MAX};

	int f[] = {0,4, 5 ,6 ,7, 8, 9, 10, 11, 12, 13,MAX};
	int A[NUM][NUM];

	for(int i=0; i<NUM; i++)
		for(int j=0; j<NUM; j++)
	{
		A[i][j]=-1;
	}
	printf("%d\n", DP_ActivitySelector(0, 11, s, f, A));
}

 

评论

2 楼 wss71104307 2008-11-09  

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000
#define NUM 13
int DP_ActivitySelector(int i, int j, int s[], int f[], int A[][NUM])
{
int k;
    int temp=0;
int max=0;
if(A[i][j] != -1) return A[i][j];

if(i == j)    return max;
else
{
for(k = i+1; k < j; k++)
{
if(s[k] < f[i] || f[k] >s[j] ) return max;
else
{
temp = DP_ActivitySelector(i, k, s, f, A) + DP_ActivitySelector(k, j, s, f, A) +1 ;

if(temp > max)
max=temp;
temp=0;
}
}
A[i][j] = max;
return max;
}
}


int Greedy_Recursion_Acitivity(int i, int j, int s[], int f[])
{
int m = i + 1;

while( m <= j && s[m] < f[i])
{
m++;
}
   
if(m > j) return 0; //递归终止条件
else return 1+Greedy_Recursion_Acitivity(m+1,j,s,f);
}


void Greedy_NonRe_Activity(int i, int j, int s[], int f[], int A[])
{
int k,l=0,m;
A[l]=i;
m=i;
for(k=i+1; k<=j; k++)
{
if(s[k]>=f[m])
{
l++;
A[l] = k;
m=k;
}
}
}

int main()
{
int i,j;
int s[] = {0,1, 3, 0, 5, 3 ,5, 6, 8 ,8 ,2 ,12,MAX};

int f[] = {0,4, 5 ,6 ,7, 8, 9, 10, 11, 12, 13,14,MAX};
   
//DP方法
int A[NUM][NUM];

for(i=0; i<NUM; i++)
for(j=0; j<NUM; j++)
{
A[i][j]=-1;
}
printf("%d\n", DP_ActivitySelector(0, 12, s, f, A));

//Greedy 1.Recursion
printf("%d\n", Greedy_Recursion_Acitivity(0, 11, s, f));
//Greedy 2.NonRecursion
//int *B=NULL;
    int B[10]={0} ;
Greedy_NonRe_Activity(1 ,11 , s, f,B);
   
for( i=0; i<sizeof(B)/sizeof(int); i++)
{
if(B[i] != 0)
printf("%d  ", B[i]);
}

return 0;
}

1 楼 wss71104307 2008-11-09  

Activity_Selector: Greedy
1.Recursion
int Greedy_Recursion_Acitivity(int i, int j, int s[], int f[])
{
int m = i + 1;

while( m <= j && s[m] < f[i])
{
m++;
}
   
if(m > j) return 0; //递归终止条件
else return 1+Greedy_Recursion_Acitivity(m+1,j,s,f);
}

2.Non_Recusion (非递归的有点问题，因为要返回活动列表，所以在主程序里面声明了一个数组A，大小为Max，初始化为0，输出的时候，只输出值不是0的元素）
void Greedy_NonRe_Activity(int i, int j, int s[], int f[], int A[])
{
int k,l=0,m;
A[l]=i;
m=i;
for(k=i+1; k<=j; k++)
{
if(s[k]>=f[m])
{
l++;
A[l] = k;
m=k;
}
}
}