dp.cpp

这是一个用动态规划算法

#include<stdio.h>
#include<stdlib.h>
#define N  3  //宏定义作业数
int p[N] ;    //p[N]表示的是最优序列的顺序
int a[N] ;    //宏定义作业在第一台机器上运行的时间
int b[N] ;   //作业在第二台机器上运行的时间

typedef struct {
	int name;
	int flag;
}JOB;

int T(int t,int i,JOB s[]) //t为等待时间, s[]为原作业集合,n为总作业数
{
	int min=0,t1=0,k=0,u=0;

	while(s[i].flag==0)
	{
	t1=t-a[i];                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
	if(t1<=0)
		t1=0;
	t1+=b[i];
	s[i].flag=1;
	t=T(t1,i+1,s);
	min=a[i]+t;
	for(k=i+1;s[k].flag==0;k++)
	{
		t1=t-a[k];
		if(t1<=0)
			t1=0;
		t1+=b[k];
		s[k].flag=1;
		t1=a[k]+T(t1,k+1,s);
		if(t1<min)
		{
			min=t1;
			u=k;
		}
	}
	p[i]=u;  
	i++;
	}
	return min;
}

void main()
{
	int t=0,i=0; 
	JOB s[N];
	FILE *fp;

	for(i=1;i<=N;i++)
	{
		s[i].name=i;
		s[i].flag=0;
	}
	fp=fopen("input.txt","r");
	if(fp==NULL)
	{
		printf("Can't open the file!");
		exit(-1);
	}
	for(i=1;i<=N;i++)
		fscanf(fp,"%d",&a[i]);
	for(i=1;i<=N;i++)
		fscanf(fp,"%d",&b[i]);
	t=T(0,1,s);     //调用函数求最短时间
	printf("%d \n",t);
	for(i=1;i<=N;i++)
		printf("%d ",p[i]);	
	fclose(fp);
}