作业排序.cpp

算法的几个程序 排序 货郎档 二分法

#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的两个集合,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 MINMUM(int n,int m)                                                       
{//求n和m的最小值   
	if(n>m)
		return m;   
	else  
		return n;   
}   

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


int FJS(int *D,int n,int b,int *J,int *Q)   
{//找J(n)的最优解，并返回最优解的个数   
	int i,*F,*p,j,l,k;   
	F=(int*)malloc((b+1)*sizeof(int));   
	p=(int*)malloc((b+1)*sizeof(int));   
	for(i=0;i<=b;i++)
	{//将树置初值   
		F[i]=i;   
		p[i]=-1;   
	}   
	k=0;//初始化J   
	for(i=1;i<=n;i++)   
	{//使用贪心规则   
		j=FIND(p,MINMUM(n,D[i]));   
		if(F[j]!=0)   
		{//选择作业i   
			k=k+1;   
			J[k]=i;   
			Q[F[j]]=i;   	//保存作业执行的正确顺序
			l=FIND(p,F[j]-1);   
			UNION(p,l,j);   
			F[j]=F[l];   
		}   
	}   
	return k;//返回最优解的个数   
}   



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]<D[j]) 
				max=D[j];   
			else  
				max=D[i];
		}
		else
		{   
			mid=(i+j)/2;   
			max1=MAX(D,i,mid);   
			max2=MAX(D,mid+1,j);   
			max=MAXMUM(max1,max2);   
		}   
	}
	return max; 
	
}   

void sort(int *D,int n)   
{//将D中的元素按非增次序分类   
	int   j,item,i;   
	D[0]=999999;   //设置监视哨   
	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;   		
	}       
}   

void main()   
{   
	int *D,*J,*Q,*p,n,b,i,k;   
	printf("作业排序的一个更快算法\n");   
	printf("请输入作业的数目:");   
	scanf("%d",&n);                     //输入作业个数
	D=(int*)malloc((n+1)*sizeof(int));   //截止天数数组
	p=(int*)malloc((n+1)*sizeof(int));   //效益数组
	printf("请输入每个作业的效益值(%d个):",n);   
	for(i=1;i<=n;i++)   
		scanf("%d",&p[i]);				//输入效益
	sort(p,n);							//效益排序
	printf("\n按效益值非增排序后各作业为:\n");   
	printf("作业序号  效益值\n");   
	for(i=1;i<=n;i++)   
		printf("J%d        %d\n",i,p[i]);		//输出排序后的效益
	printf("\n请输入按效益值非增排序后各作业的截止时间(%d个):",n);   
	for(i=1;i<=n;i++)   
		scanf("%d",&D[i]);				//输入截止天数
	b=MINMUM(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);                   //求最优解并返回作业数
	printf("\n本问题的最优解\n");   
	printf("作业序号  效益值\n");   
	for(i=1;i<=k;i++)   
		printf("J%d        %d\n",J[i],p[J[i]]);  //打印最优解 
	printf("\n各作业的执行次序\n");   
	printf("作业序号  效益值\n");   
	for(i=1;i<=b;i++)   
		if(Q[i]!=-1)   
			printf("J%d        %d\n",Q[i],p[Q[i]]);   //按执行顺序打印最优解
		printf("\n\n");   
		
}