tanxinfa.cpp

算法设计与分析中的贪心法源程序

#include <stdio.h>
#include <malloc.h>
void  sort(int *P,int *D,int n)
{              //将作业按效益值非递增次序排序
	int i,k,t;
	for(k=1;k<n;++k)
		for(i=k+1;i<=n;++i)
			if(P[k]<P[i])
			{
				t=P[k];
                P[k]=P[i];
			    P[i]=t;
			    t=D[k];
			    D[k]=D[i];
			    D[i]=t;
			}
}
void JS(int *D,int *P,int *J,int n)
{     //J[i]是最优解中的第i个作业，终止时最优解中的作业的期限值按非递减次序排序
	int i,j,k,r;
	sort(P,D,n);
    k=1;
	J[1]=1;    //计入作业1
	for(i=2;i<=n;++i)//按p的非增次序考虑作业。找i的位置并检查插入的可行性
	{
		r=k;
		while((D[J[r]]>D[i])&&(D[J[r]]!=r))
			--r;
		if((D[J[r]]<=D[i])&&(D[i]>r))
		{           //把i插入J
			for(j=k;j>=r+1;--j)
				J[j+1]=J[j];
			J[r+1]=i;
			k++;
		}
	}
	printf("最优解为:");
	printf("\n");
	for(i=1;i<=k;++i)
	{         //按顺序输出最优解中作业的期限值和效益值
		printf("第%d个作业的期限值为%d，效益值为%d",i,D[J[i]],P[J[i]]);
		printf("\n");
	}
}
void main()
{
	int n,j;
	printf("请输入作业的个数:");
	scanf("%d",&n);
	int *D,*P,*J;
	D=(int *) malloc(sizeof(int *)(n+1));
	P=(int *) malloc(sizeof(int *)(n+1));
	J=(int *) malloc(sizeof(int *)(n+1));
	D[0]=P[0]=J[0]=0;  //初始化
	printf("请输入每个作业的效益值：");
	for(j=1;j<=n;j++)
		scanf("%d",&P[j]);
    printf("请输入每个作业的期限值：");
    for(j=1;j<=n;j++)
		scanf("%d",&D[j]);
	JS(D,P,J,n);     //
}