jiqisheji.c

假定只能在一台机器上处理n个作业

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

int m,n,sw=0,sc,cs,g=0,ming,s=0,w[20][20],c[20][20];a[20];b[20];


void try(int i)
 {
	int j,t=i,x;

    for (j=0;j<m;j++)
	{
		t=i*2;
		while(t-->0)printf(" ");
		printf("部件%d",i);
		printf(" 供应商%d\n",j);
		s=s+c[i][j];
		g=g+w[i][j];
		if (i<n-1)
		{
		
			if(s<sc&&g<ming){b[i]=j;try(i+1);}
			else if(s>=sc)printf("			成本超标\n");
			else printf("			不是已知最小重量方案\n");
		}
		else 
			if(g<=ming&&s<=sc)
			{
				cs=s;
				b[n-1]=j;
				for(x=0;x<20;x++)a[x]=b[x];
				ming=g;
				printf("			重量%d  成本%d\n",g,s);
			}
   			else if(s>sc)printf("			成本超标\n");
			else printf("			不是已知最小重量方案\n");
			
		
	s=s-c[i][j];
	g=g-w[i][j];
     
	}
}

			

int main()
{
	int i,j;
	printf("请输入部件数(<=20):");
	scanf("%d",&n);
	printf("请输入供应商数(<=20):");
	scanf("%d",&m);
	
	srand((unsigned)time(NULL)); 
	
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			w[i][j]=1+rand()%5; 
			c[i][j]=1+rand()%5;
		}

	printf("零件重量矩阵:\n");
	for(i=0;i<n;i++,printf("\n"))
		for(j=0;j<m;j++)
			printf("%3d",w[i][j]);
	printf("零件成本矩阵:\n");
	for(i=0;i<n;i++,printf("\n"))
		for(j=0;j<m;j++)
			printf("%3d",c[i][j]);

	printf("请输入总成本上限:");
	scanf("%d",&sc);
	ming=n*5;

	try(0);
	if(ming<n*5)
	{
	printf("\n************最小重量方案************\n");
	for(i=0;i<n;i++)
	{
		j=a[i];
		printf("部件%d 厂商%d 部件成本%d 部件重量%d",i,j,c[i][j],w[i][j]);
		if(i<n-1)printf("\n");
	}
	printf("\n************************************\n");
	printf("成本上限:%d\n本方案成本:%d\n本方案重量:%d\n",sc,cs,ming);
	}
	else
		printf("不存在这样的方案\n");

	return 0;
}