陈锋-6分.txt

这是很不错的计算机算法

/*本程序运行前提：  在源程序目录下存在input.txt文件，并且该文件已经按一定格式存储若干值*/
#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>
class board
{  
  private:    
    int n,//电路板数 
        m,//连接块数     
        *x,//当前解     
        *bestx,//当前最优解     
        bestd,//当前最优密度     
        *total,//total[i]=连接块i的电路板数     
        *now,//now[i]=当前解中所含连接块i的电路板数     
        **b;//连接块数组   
  public:    
    board();//构造函数     
	void backtrack(int i,int cd);//递归函数     
	void ouputtofile();//输出函数     
	~board();//析构函数 
};

  void swap(int&,int&);//交换函数 

/*构造函数的定义*/ 
board::board()
{  
  int i,j;//循环控制变量   
  ifstream fin("input.txt",ios::nocreate);//打开输入文件  
  if(!fin) //如果文件不存在   
  {    
    cerr<<"文件不存在";    
	exit(-1);  
  }   
  fin>>n>>m;//读入电路板数和连接块数   
  if(!(b=new int*[n+1]))//分配二维数组b   
  {    
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出    
	exit(-1);  
  }  
  for(i=0;i<=n;i++)    
    if(!(b[i]=new int[m+1]))//为每个一维数组分配空间    
    {     
      cerr<<"insufficient memory!"<<endl;//分配不成功，退出      
	  delete[] b;      
	  exit(-1);    
    }  
  for(i=1;i<=n;i++)//读入连接块数组     
    for(j=1;j<=m;j++)      
      fin>>b[i][j];  
  if(!(x=new int[n+1]))//分配x数组   
  {    
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出    
	exit(-1);  
  }  
  if(!(bestx=new int[n+1]))//分配bestx数组  
  {    
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出    
	exit(-1);  
  }  
  if(!(total=new int[m+1]))//分配total数组  
  {    
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出    
	exit(-1);  
  }  
  if(!(now=new int[m+1]))//分配now数组  
  {    
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出    
	exit(-1);  
  }  
  for(i=1;i<=m;i++) total[i]=now[i]=0;//数组初始化   
  for(i=1;i<=n;i++)//x数组和total数组初始化   
  {    
    x[i]=i;    
	for(j=1;j<=m;j++) total[j]+=b[i][j];//计算每个连接块中的电路板数   
  }  
  bestd=m+1;//初始化   
  fin.close();//关闭输入文件
}

/*递归函数的定义*/ 
void board::backtrack(int i,int cd)//cd为当前连线密度 
{  
  int j,k;//循环控制变量   
  if(i==n)//所有电路板都已排定，此时的解必定是更优解   
  {    
	for(j=1;j<=n;j++)//设置新的bestx       
	bestx[j]=x[j];    
	bestd=cd;//设置新的bestd   
  }  
  else//未完继续选择x[j]为下一块电路板     
	for(j=i;j<=n;j++)   
	{      
		int ld=0;//ld表示跨越插槽j和插槽j+1的连线数       
		for(k=1;k<=m;k++)      
		{        
			now[k]+=b[x[j]][k];//更新now数组         
			if(now[k]>0&&total[k]!=now[k]) ld++;//如果连接块k跨越插槽j和插槽j+1，连线数加1       
		}      
		if(cd>ld) ld=cd;//如果此时连线数更小，则连线密度应取更大值       
		if(ld<bestd)//如果此时的连线密度还未超过最优值，可以继续递归搜索子树       
		{        
			swap(x[i],x[j]);//交换两电路板位置         
			backtrack(i+1,ld);//递归搜索         
			swap(x[i],x[j]);//还原电路板位置以便考虑下一种排列情况       
		}      
		for(k=1;k<=m;k++) now[k]-=b[x[j]][k];//now数组还原为选择x[j]电路板之前的情况     
	}
}

/*输出函数的定义*/ 
void board::ouputtofile()
{  
	ofstream out("output.txt");//创建输出文件  
	out<<bestd<<endl;//输出最小密度   
	for(int i=1;i<=n;i++)  
	{    
		out<<bestx[i]<<" ";//输出最优解信息   
	}  
	out.close();//关闭输出文件 
}

/*析构函数的定义*/ 
board::~board()
{  
	delete[] x;//释放x所占内存   
	delete[] bestx;//释放bestx所占内存  
	delete[] total;//释放total所占内存  
	delete[] now;//释放now所占内存   
	for(int i=0;i<=n;i++)//释放二维b数组所占内存     
		delete[] b[i];  
	delete[] b;
}

/*主程序部分*/ 
int main()
{  
	board boa;//创建类board的实例   
	boa.backtrack(1,0);//调用递归函数计算最小密度   
	boa.ouputtofile();//输出解信息   
	return 0;
}
/*交换函数的定义*/ 
void swap(int& a,int& b)
{  
	int temp;  
	temp=a;  
	a=b;  
	b=temp;  
}