Activity selection problem, activity selection_PHP tutorial

Activity selection problem, activity selection

Problem description:

Suppose there is a set of n activities E={1,2,…,n}. Each activity requires the use of the same resource, such as a lecture venue, etc., and only one activity can use this resource at the same time. . Each activity i has a start time si that requires the use of the resource and an end time fi, and si < fi. If activity i is selected, it occupies resources within the half-open time interval [si, fi). If the interval [si, fi) and the interval [sj, fj) do not intersect, then activity i and activity j are said to be compatible. That is to say, when si≥fj or sj≥fi, activity i is compatible with activity j. The activity scheduling problem is to select the largest compatible activity sub-set from the given activity set.

.

It can be seen from the figure that there are 11 activities in S. The largest mutually compatible activity subset is: {a₁, a₄, a₈ , a11,} and {a₂, a₄, a₉, a₁₁}.

2. Dynamic programming solution process

(1) Optimal substructure of activity selection problem

Define the sub-problem solution space S_ij to be a subset of S, each of which is compatible with each other. That is, each activity starts after a_i ends and ends before a_j starts.

In order to facilitate discussion and subsequent calculations, add two fictitious activities a₀ and a_{n 1,} where f₀=0, s_{n 1}=∞.

Conclusion: When i≥j, S_ij is the empty set.

If activities are ordered monotonically increasing by end time, the subproblem space is used to select the largest compatible subset of activities from S_ij, where 0≤i＜j≤n 1, so the other S_ij are all empty sets.

The optimal substructure is: Assume that the optimal solution A_ij of S_ij contains activity a_k, then for S _{The solution A}ik _{of ik} and the solution A_kj of S_kj must be optimal.

The problem is divided into two sub-problems through an activity a_k. The following formula can calculate the solution A_ij of S_ij.

(2) A recursive solution

Let c[i][j] be the number of activities in the largest compatible subset of S_ij. When S_ij is the empty set, c[i][j] =0; when S_ij is non-empty, if a_k is used in the largest compatible subset of S_ij, then the problem S_{ik The maximum compatible subset of} and S_kj is also used, so we can get c[i][j] = c[i][k] c[k][j] 1.

When i≥j, S_ij must be the empty set, otherwise S_ij needs to be calculated according to the formula provided above. If a<🎜 is found >k_{, then S}ij _{is non-empty (at this time, f}i_≤sk _{and f}k_≤sj_{), if such a}k _{cannot be found, then S}ij _{is the empty set.}

The complete calculation formula of c[i][j] is as follows:

Personal test code: 1 #include 2 #define max_size 10010 3 int s[max_size]; 4 int f[max_size]; 5 int c[max_size][max_size]; 6 int ret[max_size][max_size]; 7 8 using namespace std; 9 10 void DP_SELECTOF(int *s,int *f,int n,int c[][max_size],int ret[][max_size]) 11 { 12 int i,j,k; 13 int temp; 14 for(j=2;j<=n;j ) 15 for(i=1;i) 16 { 17 for(k=i 1;k) 18 { 19 if(s[k]>=f[i]&&f[k]<=s[j]) 20 { 21 temp=c[i][k] c[k][j] 1; 22 if(c[i][j]<temp) 23 { 24 c[i][j]=temp; 25 ret[i][j]=k; 26 } 27 } 28 } 29 } 30 } 31 32 int main() 33 { 34 int n; 35 printf("输入活动个数 n: "); 36 while(~scanf("%d",&n)) 37 { 38 memset(c,0,sizeof(0)); 39 memset(ret,0,sizeof(ret)); 40 printf("n输入活动开始以及结束时间n"); 41 int i,j; 42 for(i=1;i<=n;i ) 43 { 44 scanf("%d%d",&s[i],&f[i]); 45 } 46 DP_SELECTOF(s,f,n,c,ret); 47 printf("最大子集的个数=%dn",c[1][n] 2); 48 return 0; 49 } View Code

下面是贪心法的代码：

  

1 #include 2 #define max_size 10010 3 int s[max_size]; 4 int f[max_size]; 5 int ret[max_size]; 6 int c[max_size][max_size]; 7 using namespace std; 8 9 void GREEDY_ACTIVITY_SELECTOR(int *s,int *f,int n,int *ret) 10 { 11 int k,m; 12 *ret =1; 13 k=1; 14 for(m=2;m<=n;m ) 15 if(s[m]>=f[k]) 16 { 17 *ret =m; 18 k=m; 19 } 20 } 21 int main() 22 { 23 int n; 24 printf("输入活动个数 n: "); 25 while(~scanf("%d",&n)) 26 { 27 memset(s,0,sizeof(s)); 28 memset(f,0,sizeof(f)); 29 memset(c,0,sizeof(0)); 30 memset(ret,0,sizeof(ret)); 31 printf("n输入活动开始以及结束时间n"); 32 int i,j; 33 for(i=1;i<=n;i ) 34 { 35 scanf("%d%d",&s[i],&f[i]); 36 } 37 GREEDY_ACTIVITY_SELECTOR(s,f,n,ret); 38 for(i=0;i<=n;i ) 39 { 40 if(ret[i]!=0) 41 printf("a%d ",ret[i]); 42 } 43 printf("n"); 44 } 45 } View Code

 

http://www.bkjia.com/PHPjc/1069127.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/1069127.htmlTechArticle活动选择问题，活动选择 问题描述： 设有n个活动的集合E={1,2,,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有...