cpp1.cpp

这是基于VC++的一个简单的流水作业程序(动态规划法)

#include <iostream.h>
#include  <stdio.h> 
class Jobtype
{
public:
	int key,index;
	bool job;
};
void Sort(Jobtype *d,int p,int r);
void Swap(Jobtype a,Jobtype b);
int Partition(Jobtype *d,int p,int r);
void main()
{
	int n=5;
  int *a=new int[n];
  int *b=new int[n];
  cout<<"作业集N中含有5个作业！"<<endl;
  cout<<"请输入作业在机器M1上的工作时间："<<endl;
  for(int i=0;i<n;i++)
	  cin>>a[i];
  cout<<"请输入作业在机器M2上的工作时间："<<endl;
  for(i=0;i<n;i++)
	  cin>>b[i];
	Jobtype *d=new Jobtype[n];
	for(i=0;i<n;i++)
	{
		if(a[i]>b[i])  
		{ 	d[i].key=b[i];
			d[i].job=false;
		}
		else   
		{	d[i].key=a[i];
            d[i].job=true;
		}
		d[i].index=i;
	}
    Sort(d,0,n-1);
	int *c=new int[n]; 
	int j=0,k=n-1;
	for(i=0;i<n;i++)
	{
		if(d[i].job)  c[j++]=d[i].index;
		else c[k--]=d[i].index;
	}
	j=a[c[0]];
	k=j+b[c[0]];
	for(i=1;i<n;i++)
	{  	j+=a[c[i]];
		if(j<k) k=k+b[c[i]];
		else k=j+b[c[i]];
	}
	cout<<"此作业集的最佳调度顺序应为："<<endl;
    for(i=0;i<n;i++)
	{
		if(i!=n-1)
			cout<<"作业"<<c[i]+1<<"-->";
		else 
			cout<<"作业"<<c[i]+1<<endl;
	}
	delete d;
	getchar();
}
void Sort(Jobtype *d,int p,int r)
{
    if(p<r)
	{
		int q=Partition(d,p,r);
        Sort(d,p,q-1);  
		Sort(d,q+1,r);  
	}
}
void Swap(Jobtype a,Jobtype b)
{ 
	Jobtype temp;
	temp.key=a.key;	
	a.key=b.key;
	b.key=temp.key;
	temp.job=a.job;
	a.job=b.job;
	b.job=temp.job;
	temp.index=a.index;
	a.index=b.index;
	b.index=temp.index;
}
int Partition(Jobtype *d,int p,int r)
{
	int i=p;
	int j=r+1;
    Jobtype  x=d[p];
	while(true)
	{
		while(d[++i].key<x.key); 
        while(d[--j].key>x.key);
		if(i>=j)break;
		Swap(d[i],d[j]);
	} 
	d[p]=d[j];
	d[j]=x;
	return j;
}