041321239.cpp

电路板排列算法

/*----------------------------文件头--------------------------------
  作者:林斌
  学号:041321239
  Email:[e-mail]
  作业名称：电路板排列问题
  
  问    题：电路板排列问题
  描    述：

  编程任务：
            
  数据输入：
  结果输出：

  编程思路：

  实现思路：

-------------------------------------------------------------------*/


#include <iostream.h> 
#include <fstream.h>
#include <stdio.h> 

void Swap(int &,int &);//交换

//--------------------- 变量、函数定义 开始 ------------------

//ofstream myoutf("output.txt");              //输出到文件,全局变量

//--------------------- 变量、函数定义 结束 ------------------

//--------------------- 类Board定义 开始 ------------------
class Board
{
  friend Arrangement(int * *,int,int,int * &);
  private:
	  void Backtrack(int i,int cd);
	  int n,		//电路板数
		  m,		//连接块数
		  * x,		//当前解
		  * bestx,	//当前最优解
		  bestd,	//当前最优密度
		  * total,	//total[j] = 连接块j的电路板数
		  * now,	//now[j] = 当前解中所含连接块j的电路板数
		  * * B;	//连接块数组
};//class Board


void Board::Backtrack(int i,int cd)
{//回溯搜索排列树
	if (i == n)
	{
		for (int j=1;j <= n;j++)
			bestx[j] = x[j];
		bestd = cd;	
	}//if
	else
		for(int j=i;j <= n;j++)
		{//选择x[j]为下一块电路板
			int ld = 0;
			for(int k=1;k <=m; k++)
			{
				now[k] += B[x[j]][k];
				if (now[k] > 0 && total[k]!=now[k])
					ld++;
			}//for
			
			//更新ld
			if (cd > ld) ld = cd;
			if (ld < bestd)
			{
				Swap(x[i],x[j]);
				Backtrack(i + 1,ld);
				Swap(x[i],x[j]);
			}// if (ld < bestd)

			
			for (k = 1; k <= m; k++)
				now[k] -= B[x[j]][k];
		}//for


}//void Board::Backtrack

int Arrangement(int * * B,int n,int m,int * & bestx)
{
	Board X;
	//初始化X
	X.x = new int [n + 1];
	X.total = new int [m + 1];
	X.now = new int [m + 1];
	X.B = B;
	X.n = n;
	X.m = m;
	X.bestx = bestx;
	X.bestd = m + 1;

	//初始化total 和 now

	for (int i = 1; i <= m; i++)
	{
		X.total[i] = 0;
		X.now[i] = 0;
	}//for

	//初始化x为单位排列并计算total
	for (i=1; i <= n ; i++ )
	{
		X.x[i] = i;
		for (int j = 1; j <= m; j++)
			X.total[j] += B[i][j];
	}//for

	//回溯搜索
	X.Backtrack(1,0);
	delete [] X.x;
	delete [] X.total;
	delete [] X.now;
	X.B = NULL ;
	X.bestx = NULL;

	//myoutf << X.bestd << endl;

	//for (i=1; i <= n; i++)
		//myoutf << bestx[i] << " ";
	return X.bestd;

}

//--------------------- 主函数 开始 --------------------------

void main()
{
	int i , j;		//循环变量
	int m , n;		//m：连接块数  n：电路板数
	int * * p;		//连接块数组
	int * bestx;	//保存当前最优解

	
	ifstream myinf("input.txt",ios::nocreate);  //读取文件
	ofstream myoutf("output.txt");              //输出到文件,全局变量

	if (myinf.fail())
	{
		cerr << "读入文件时，出错！";
		return;                                 //如果没有输入文件，则返回错误
	}//if (myinf.fail()) 

	myinf >> n >> m;

	n = n + 1;
	m = m + 1;
	//----------- 创建保存当前最优解的数组 -----------
	bestx = new int [n];
	for(i = 0; i < n; i++)
	{
		bestx[i] = i;
		cout << bestx[i] << " ";
	}
	cout << endl;
	
	//----------- 定义二维动态数组 开始 --------------
	p = new int * [n];      //给一维数组动态分配内存
	for (i=0 ; i < n; i++)
	{ 
		p[i] = new int [m];
	}//for 分配二维数组空间
	
	for (i=1 ; i < n; i++)   //给数组初始化
	{
		for (j = 1; j < m ; j++)
		{
			myinf >> p[i][j] ;
			cout << p[i][j] << " ";
		}//for j
		cout << endl;
	}//for i
		
	//----------- 定义二维动态数组 结束 --------------

	//--- 输出电路板最佳排列的密度 ---
	myoutf << Arrangement( p, n-1, m-1, bestx ) << endl;
	//--- 输出电路板的最佳排列 ---
	for (i = 1; i < n ; i++ )			
		myoutf << bestx[i] << " ";

	
	//--------释放数组---------
	for(i=0;i < n ; i++) delete[] p[i];
	
	delete[] p;                        //释放二维数组空间
	delete[] bestx;

	myinf.close();                     //关闭输入文件
	myoutf.close();                    //关闭输出文件


}//main


//--------------------- 主函数 结束 --------------------------

/*------------------------------------------------------------
 函数:Swap
 功能:交换两个数
 
 ------------------------------------------------------------*/
void Swap(int & a, int & b)
{
	int temp = a;
	a = b;
	b = temp;

}