dlbpl.h

回溯算法中的电路板问题

#include "iostream.h"

class Board
{
public:
	Board(int nn,int mm,int **bb,int *xx);
	~Board();
	void swap(int &a,int &b);
	void backtrack(int i,int dd);
	void print();
private:
	int n,m,bestd;
	int *x,*bestx,*total,*now;
	int **b;
};

Board::Board(int nn,int mm,int **bb,int *xx)
{
	n=nn;
	m=mm;
	x=new int[n+1];
	bestx=xx;
	total=new int[m+1];
	now=new int[m+1];
	bestd=m+1;
	b=bb;
	for(int h=1;h<=m;h++)
	{
		total[h]=0;
		now[h]=0;
	}
	for(int i=1;i<=n;i++)
	{
		x[i]=i;
		for(int j=1;j<=m;j++)
			total[j]+=b[i][j];
	}
}

Board::~Board()
{
	delete []x;
	delete []total;
	delete []now;
}

void Board::swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}

void Board::backtrack(int i,int dd)
{
	if(i==n)
	{
		for(int j=1;j<=n;j++)
			bestx[j]=x[j];
		bestd=dd;
	}
	else
		for(int j=i;j<=n;j++)
		{
			int d=0;
			for(int k=1;k<=m;k++)
			{
				now[k]+=b[x[j]][k];
				if(now[k]>0 && total[k]!=now[k])
					d++;
			}
			if(dd>d)
				d=dd;
			if(d<bestd)
			{
				swap(x[i],x[j]);
				backtrack(i+1,d);
				swap(x[i],x[j]);
			}
			for(int h=1;h<=m;h++)
				now[h]-=b[x[j]][h];
		}
}

void Board::print()
{
	cout<<"电路板最佳排列的密度："<<bestd<<endl;
}