一个更快的带有期限的作业排序问题

#include #include #include

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; }

int FJS(int *D,int n,int b,int *J,int {//找J(n)的最优解，并返回最优解的个数 int i,*F,*p,j,l,m,k;

F=(int *)malloc((b+1)*sizeof(int)); p=(int *)malloc((b+1)*sizeof(int));

*Q) for(i=0;i <=b;i++){//将树置初值 F[i]=i; p[i]=-1; }

k=0;//初始化J for(i=1;i <=n;i++) {//使用贪心规则

j=FIND(p,MIN(n,D[i])); if(F[j]!=0)

{//选择作业i k=k+1; J[k]=i;

Q[F[j]]=i; m=F[j];

l=FIND(p,F[j]-1); UNION(p,l,j); F[j]=F[l]; } }

return k;//返回最优解的个数 }

int MAXMUM(int i,int j) {//求i和j的最大值 if(i> j) return i; else return j; }

int MAX(int *D,int i, int j)

{//D(1:n)是含有n个元素数组，求出D(i,j)中的最大值并返回 int max,mid,max1,max2; if(i==j) max=D[i]; else if(i==j-1)

if(D[i]

mid=(i+j)/2;

max1=MAX(D,i,mid); max2=MAX(D,mid+1,j);

max=MAXMUM(max1,max2); }

return max;

}

void Insertionsort(int *D,int n) {//将D中的元素按非增次序分类 int j,item,i;

D[0]=65525; //设置监视哨 for(j=2;j <=n;j++){ item=D[j]; i=j-1;

while(item> D[i]){ D[i+1]=D[i]; i=i-1; }

D[i+1]=item; } }

int main() {

int *D,*J,*Q,*p,n,b,i,k;

cout<<\ 用贪心法解决带有限期的作业排序问题cout<

cout<< \请输入作业的数目: \ cin>>n;

D=(int*)malloc((n+1)*sizeof(int)); p=(int*)malloc((n+1)*sizeof(int));

cout<<\请输入每个作业的效益值 \ for(i=1;i <=n;i++) cin>>p[i];

Insertionsort(p,n);

cout<<\按效益值非增排序后各作业为: \ cout<<\作业序号效益值\ for(i=1;i <=n;i++)

cout<<\ \ \

cout<< \请输入按效益值非增排序后各作业的截止时间: \for(i=1;i <=n;i++) cin>>D[i];

b=MIN(n,MAX(D,1,n));

J=(int*)malloc((b+1)*sizeof(int)); Q=(int*)malloc((b+1)*sizeof(int)); for(i=1;i <=b;i++) Q[i]=-1;

\ k=FJS(D,n,b,J,Q);

cout<< \本问题的最优解---------------------------------\cout<<\作业序号\ \效益值\ for(i=1;i <=k;i++)

cout<

cout<< \各作业的执行次序-------------------------------\ cout<<\作业序号\ \效益值 \ for(i=1;i <=b;i++) if(Q[i]!=-1)

cout<

\