/*
   開發思想：先用窮舉法搜索，也就是用一個組合的思想，把所有可
			 能的情況列出，并不斷地進行比較判斷，判斷后不斷地
			 進行剪枝，以減少算法的運行時間，剪枝越多，算法就
			 越好。
   開發人員：葛興高
   開發日期：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;
	}
  }
}