maxprofit.cpp

里面装有 5 个小程序

/*
   开发思想：先用穷举法搜索，也就是用一个组合的思想，把所有可
			 能的情况列出，并不断地进行比较判断，判断后不断地
			 进行剪枝，以减少算法的运行时间，剪枝越多，算法就
			 越好。
   开发人员：葛兴高
   开发日期：2004、01、16
   开发版本：1.0
*/
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#include  <math.h>

const n=30;
const m=10;

class Maxprofit
{
	private:
		int A[n+1][m+1];//定义二维数组，用于记录所产生的数值
		int f[n+1][m+1];//定义二维数组，用于所产生的最优解值
		int pro[11];
		int jiqi[11];
	public:
		void Mprofit();//构造函数
		void RandA();//随机产生一个矩阵 
		void CinA();//手动输入一个矩阵
		void CoutA();//输出这个矩阵
};

void Maxprofit::CoutA()
{
	for(int i=1;i<n+1;i++)
	{
		for(int j=1;j<m+1;j++)
		{
			cout<<A[i][j]<<"\t";
			//输入n*m阶矩阵，当i=0或j=0是默认为内存，不存任何数
		}
	}
}
void Maxprofit::CinA()
{
	int j,i;
	for(i=0;i<n+1;i++)   
	for (j=0;j<m+1;j++) 
	{
		A[i][j]=0;
	}//初始化矩阵为0
	for(i=1;i<n+1;i++)
		for(j=1;j<m+1;j++)
			cin>>A[i][j];
}

void Maxprofit::RandA()
{
	int i,j;
	srand((unsigned)time(NULL));//用于为rand函数提供随机种子
	for(i=0;i<n+1;i++)   
	for (j=0;j<m+1;j++) 
	{
		A[i][j]=0;
	}//初始化矩阵为0
	for(i=1;i<n+1;i++)
		for(j=1;j<m+1;j++)
		{
			A[i][j]=rand()%1000;
		}
}
void Maxprofit::Mprofit( )
{
	int i,j;//i表示机器数，j表示车间数 
	for(i=0;i<n+1;i++) 
		for (j=0;j<m+1;j++) 
		{
			f[i][j]=0;
		}
	/*如果用下面这一方法定义的话，那将会在循环输入时出错，
	因为其中它保存着最大值，如果没有新的最大值出现，其将
	会一直显示旧的结果。从而不能看到每一次运行的最优解。
	for(i=0;i<n+1;i++)   
		f[i][0]=0;
	for (j=0;j<m+1;j++) 
	  f[0][j]=0;
	*/
	for(i=1;i<n+1;i++)//必须从1开始
	{
		for(j=1;j<m+1;j++)//必须从1开始  
		{
			int k=0;
			while(k<i+1)//f[i][j]表示i个车间分配j台机器是的最大盈利
			{
				if(f[i][j]>(f[i-k][j-1]+A[k][j]))
				{
					k++;  
				}
				else 
				{
					f[i][j]=f[i-k][j-1]+A[k][j]; 
					k++; 
				} 
			}
		}
	}
	int d=30;//30台机器
	for(int c=10;c>0;c--)//从第十个车间开始循环
	{
		int a,u;
		for(int e=d;e>=0;e--)
		if ((f[e][c-1]+A[d-e][c])==f[d][c])//循环调用
		{ 
			a=d-e;
			u=A[d-e][c];
			break;
		}
		d=e;
		jiqi[c]=a;
		pro[c]=u;
		//cout<<"第"<<c<<"个车间"<<"\t";
		//cout<<"分配机器台数为:"<<a<<"\t";
		//cout<<"此时利润为:"<<u<<endl;
	}
	for(int q=1;q<11;q++)
	{
		cout<<"第"<<q<<"个车间"<<"\t";
		cout<<"分配机器台数为:"<<jiqi[q]<<"\t";
		cout<<"此时利润为:"<<pro[q]<<endl;
	}
	cout<<"最大的盈利可以是:"<<f[n][m]<<endl; 
	/*for(i=1;i<n+1;i++)//输出各个最优方案的结果
		for (j=1;j<m+1;j++)
			cout<<f[i][j]<<"\t";*/
}


void main()
{
	LARGE_INTEGER  litmp;
	LONGLONG  Start, End;
	double dfMinus, dfFreq, kst;
	int choice=1;
	Maxprofit p;
	while(choice!=0)
	{
	cout<<"1...随机输入"<<endl;
	cout<<"2...自己输入"<<endl;
	cout<<"0...退出"<<endl;
	cin>>choice;
	
	switch(choice)
	{
	case 1:p.RandA();
		   p.CoutA();
		   cout<<"最优解的分配方案如下:"<<endl;
		   {
		QueryPerformanceFrequency( &litmp );
		dfFreq = (double)litmp.QuadPart;
		QueryPerformanceCounter( &litmp );
		Start = litmp.QuadPart;
		p.Mprofit();
		QueryPerformanceCounter( &litmp );
		End = litmp.QuadPart;
		dfMinus = (double)( End - Start );
		kst = (dfMinus / dfFreq ) * 1000;
		cout<<"所用的时间为:"<<kst<<"毫秒"<<endl;
		  //也可以用以下这种方法计算时间，但不够精确。
		  /*clock_t start=clock();
		   p.Mprofit();
		   clock_t finish=clock();
		   cout<<"所用的时间为:"<<(double)(finish-start)/ CLOCKS_PER_SEC<<"毫秒"<<endl;*/
         }
		break;
	case 2:p.CinA();
		   p.CoutA();
		   p.Mprofit();
		break;
	case 0:
		break;
	}
  }
}