工作安排.cpp

经典算法之换位和工作安排

#include <iostream.h>


void Swap(int &a ,int &b)
{
	int temp=a;a=b;b=temp;
}



void Perm(int list[],int k, int m,int &bestp,int bestList[])
{
	int work[3][3]={2,1,4,3,5,3,5,3,2};
	int currentp=0;
	if((k>=m)&&(list[m]>list[0]))
	{
		for(int i=0;i<m;i++)
		{
			cout<<list[i];
			currentp+=work[i][list[i]-1];
		}
		cout<<endl;
		if(currentp<bestp)
		{
			for(i=0;i<m;i++)
				bestList[i]=list[i];
			bestp=currentp;
		}
	}
	else
		for(int i=k;i<m;i++)
		{
			Swap(list[k],list[i]);
			Perm(list,k+1,m,bestp,bestList);
			Swap(list[k],list[i]);
		}
}



void main()
{
	int list[]={1,2,3},m=3;
	int bestp=100;
	int *bestList =new int [m];
	for(int i=0;i<m;i++)
		bestList[i]=0;
	Perm(list,0,m,bestp,bestList);
	cout<<"best price:"<<bestp<<endl;
	for(i=0;i<m;i++)
		cout<<"工作"<<i<<"由第"<<bestList[i]<<"来完成"<<endl;
}