job.cpp

来自「内有5个常用算法」· C++ 代码 · 共 60 行

#include <stdio.h>
#define max 100
int job[max][2],x[max],bestf,bestx[max],n,f2[max]={0},f1,t;
int c=1,f=0,tag[100];

void execute(int i)
{
   int j;
   if(i>n)
   {
	   if(bestf>f)
	   {
		   bestf=f;
		   for(j=1;j<=n;j++)
			   bestx[j]=x[j];
	   }
   }
   else
	   {
		   for(j=1;j<=n;j++)
		   {
			   if(tag[j]==0)
			   {
				   tag[j]=1;
				   x[c]=j;
				   c++;
				   f1=f1+job[j][1];
				   f2[j]=((f2[j-1]>f1)?f2[j-1]:f1)+job[j][2];
				   f=f+f2[j];
				   execute(i+1);
				   f=f-f2[j];
				   c--;
				   f2[j]=0;
				   tag[j]=0;
				   f1=f1-job[j][1];
			   }
		   }
	   }
}

void main()
{
	int i,j;
	f1=0;
	scanf("%d",&n);
	for(j=1;j<=n;j++)
		for(i=1;i<3;i++)
		{
			scanf("%d",&job[j][i]);
		}
	bestf=32767;
	for(i=1;i<=n;i++)
		tag[i]=0;
	execute(1);
	for(i=1;i<n;i++)
		printf("%d->",bestx[i]);
	printf("%d\n",bestx[n]);
	printf("%d\n",bestf);

}