fjs最优解0.cpp

按作业效益非增序输入作业的截止期限

#include<stdio.h>
void UNION(int i,int j,int parent[])
//使用加权规则合并根为i和j的两个集合，(i!=j)//
//PARENT(i)=-COUNT(i);PARENT(j)=-COUNT(j)//
{
	int x;
	x=parent[i]+parent[j];
	if(parent[i]>parent[j])
	{
		parent[i]=j;                  //i的结点少//
		parent[j]=x;
	}
	else 
	{
		parent[j]=i;                 //j的结点少//                
		parent[i]=x;
	}
}

int FIND(int i,int parent[])
//查找含有元素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 FJS(int D[],int n,int J[],int F[])
//找最优解J(1:k)//
//假定p1>=p2>=...>=pn//
{
	int e,t,l,i,j;
	int k;
	int parent[256];
	for(e=0;e<=n;e++)
	{
		parent[e]=-1;
	}
	k=0;                           //初始化J//
	for(i=1;i<=n;i++)
	{
		t=(n<=D[i])?n:D[i];        //使用贪心原则// 
		j=FIND(t,parent);
		if(F[j]!=0) 
		{
			k++;
			J[k]=i;                //选择作业i//
			l=FIND(F[j]-1,parent);
			UNION(l,j,parent);
			F[j]=F[l];
		}
	}
}

void main()
{
	int J[256];                      //J[k]存放作业 
	int D[256];                      //D[k]为截止期限 
	int p[256];                      //P[k]为效益值 
	int F[256];                      //对每个期限值i,当前最接近的空时间片为F[i]
	int e;
	int n;
	printf("***************更快的作业排序算法FJS**************\n");
	printf("*****(假设作业已经按效益p的非递减排过序)**********\n");
	printf("****(所以为保证正确的结果请按p非增序输入作业)*****\n");
	printf("请输入作业的个数:");
	scanf("%d",&n);
	while(n<=0)
	{  
		printf("输入错误，请输入一个正整数：");
		scanf("%d",&n);
	} 
  
	for(e=0;e<=n;e++)
	{
		F[e]=e;
	}
	for(e=1;e<=n;e++)
	{
		J[e]=-1;
	}
	for(e=0;e<n;e++)
	{
		printf("请依次输入作业在截止期限前完成可以得到的最大效益:");
		scanf("%d",&p[e]);
	}
	for(e=1;e<=n;e++)
	{
		printf("请依次输入作业的截止期限:");
		scanf("%d",&D[e]);
		while(D[e]<=0)
		{  
			printf("输入错误，请输入一个正整数：");
			scanf("%d",&D[e]);
		} 
	}
	FJS(D,n,J,F);
	printf("更快的作业排序算法FJS求解得到的最优解为:\n");
	for(e=1;e<=n&&J[e]!=-1;e++)
		printf("%-4d",J[e]);
}