计算机算法基础贪心算法带有限期的作业问题

算法设计思想：如果J是作业的可行子集，那么可以使用下述规则来确定这些作业中的每一个作业的处理时间：若还没给作业i分配处理时间，则分配给它时间片[a-1,a]，其中a应尽量取最大且时间片[a-1,a]是空的。此规则就是尽可能推迟对作业i的处理。于是，在将作业一个一个地装配到J中时，不必为接纳新作业而去移动J中那些已分配了时间片的作业。如果正被考虑的新作业不存在像上面那样定义的a，这个作业就不能计人J。各作业的效益值放在P[   ]中，并按效益值非增次序排列，期限值放在D[   ]中，F[   ]用于存放最大期限值，J[   ]用于存放最优解，Q[   ]用于存放作业的调度次序。   
    
  算法描述：   
  line   procedure     FJS(D,n,b,j,   k)       
            //找最优解J=J（1），…J（K）//   
              //D(1),…..,D(n)是期限值,n>=1.作业已按//P(1)>=P(2)>=….P(n)被排序，//b=min{n,max{D(i)}}//   
  integer   b,i,k,n,j   ,l,D(n),J(n),F(0:b),p(0:b)   
  for   i=1to   n   do         //将树置初值//   
                F（i）ßi;p(i)ß-1   
  repeat   
  Kß0         //初始化J//   
  for     iß1   to     n     do           //使用贪心规则//   
                  jß   FIND(min(n,D(i)   ))   
                  if   F(j)不为０   then   kßk+1;J(K)ßi         //选择作业   i//   
                                      lßFIND(F(j)-1);   call   UNION(l,j)   
                                      F(j)ßF(1)   
                endif   
  repeat   
  end   FJS   
    
  算法分析：此算法的时间复杂度为:O(na(2n,n))（Ackerman函数的逆函数。）；   
  　　　　　它用于Ｆ和Ｐ的空间至多为２n个字节。   
    
  完整的代码（C语言）：   
  #include<stdio.h>   
  #include<malloc.h>   
    
  int   FIND(int   *parent,int   i)   
  {//查找含有元素i的树根，使用压缩规则去压缩由i到根j的所有结点   
  int   j,k,t;   

  j=i;   
  while(parent[j]>0)   j=parent[j];//找根   
  k=i;   
  while(k!=j){//压缩由i到根j的结点   
  t=parent[k];   
  parent[k]=j;   
  k=t;   
  }   
  return   j;   
  }   
    
  void   UNION(int   *parent,int   i,int   j)   
  {//使用加权规则合并根为i和j的两个集合   
  int   x;   
  x=parent[i]+parent[j];   
  if(parent[i]>parent[j]){//i的结点少   
  parent[i]=j;   
  parent[j]=x;   
  }   
  else{//j的结点少   
  parent[j]=i;   
  parent[i]=x;   
  }   
  }   
    
  int   MIN(int   n,int   m)                                                       
  {//求n和m的最小值   
  if(n>m)   return   m;   
  else         return   n;   
  }