学步园

一、类CExactCoverSolution的声明

#include<vector>
#include<string>
#include <algorithm>
#include <iostream>
using namespace std;

//类型的定义
typedef int ELEMENT_TYPE;
typedef char SUBSET_NAME; 
typedef vector<int> ROW;
typedef vector<ROW> MATRIX;
typedef vector<ELEMENT_TYPE> FULL_SET;
typedef vector<SUBSET_NAME> SUBSET_NAMES;
typedef SUBSET_NAMES SOLUTION;

class CExactCoverSolution
{
public:
	CExactCoverSolution(const MATRIX& matrix
		,const SUBSET_NAMES& names
		);

	~CExactCoverSolution(void);

	const MATRIX& m_matrix;    //0-1矩阵
	SOLUTION  m_solution;      //当前可行解
	const SUBSET_NAMES& m_subsetNames;   //子集的名字
	
	const int m_elementNum;    //元素的个数
	const int m_subsetNum;     //子集的数目

	
	//计算某一列的和
	int GetColumnCount(int columnIndex)const;
	int  GetMinColumnIndex(int &sum)const; //找出含1个数最少的列号
	
	//判断某一行是否全1
	bool isFullOneRow(int rowIndex) const;
	int getFullOneRow()const;

	//获取和第c列相交或者不的所有行
	void getRowNos(const int c,vector<int>& rows,int value=1)const;

	//获取和第r行相交或者不相交的所有列
	void getColumnNos(const int r,vector<int>& columns,int value=1)const;

	//获取和第r行无公共元素的各行
	void getOtherRows(const int r,vector<int>& otherrows)const; 

	//在旧矩阵中去掉所有和row相交的行和列，获得新的矩阵，
	void getNewMatrix(const vector<int>& rows,const vector<int>& columns,MATRIX& matrix)const;

	void getNewNames(const vector<int>& rows,SUBSET_NAMES& names)const;

public:
	bool search();  //求解
	
public:
	void print(ostream&os=cout)const;
	
};

二、实现

#include "ExactCoverSolution.h"

CExactCoverSolution
	 ::CExactCoverSolution(const MATRIX& matrix
					,const SUBSET_NAMES& names
					)
		:m_matrix(matrix)
		,m_subsetNames(names)
		,m_elementNum(matrix[0].size())
		,m_subsetNum(matrix.size())
{
	
}

CExactCoverSolution::~CExactCoverSolution(void)
{
}

int CExactCoverSolution::GetMinColumnIndex( int &sum ) const
{
	int ColumnIndex=0;
	sum=GetColumnCount(ColumnIndex);

	for(int i=1;i<m_elementNum;++i)
	{
		int newSum=0;
		if ((newSum=GetColumnCount(i))<sum)
		{
			sum=newSum;
			ColumnIndex = i;
		}
	}
	return ColumnIndex;
}



bool CExactCoverSolution::search() 
{
	bool flag = false;
	int rowIndex=-1;
		
	//如果矩阵为空，则说明所有元素已经被得到已经得到可行解。
	if (m_matrix.size()==0) 
		flag=true;

	//如果有全1的行，则将该行加入到可行解中，并返回真
	else if ((rowIndex=getFullOneRow())>=0)
	{
		m_solution.push_back(m_subsetNames[rowIndex]);
		flag =true;
	}
	
	else 
	{
		int sum=0;
		int c =GetMinColumnIndex(sum);
		
		if (sum==0)
			flag =false; //如果有全0的列，则说明此时一定无解
		else
		{
			//得到和第c列相交的所有行列表
			vector<int> rows;
			getRowNos(c,rows);

			for(int i=0;i<rows.size();++i)
			{
				int r=rows[i];
																
				//得到和本行不相交的所有列
				vector<int > columns;
				getColumnNos(r,columns,0);


				vector<int > other;
				getOtherRows(r,other);

				SUBSET_NAMES names;
				getNewNames(other,names);

				MATRIX matrix;
				getNewMatrix(other,columns,matrix);

				CExactCoverSolution s(matrix,names);
				flag = s.search();
				if (flag)
				{
					m_solution.push_back(m_subsetNames[r]);
					m_solution.insert(m_solution.end(),s.m_solution.begin(),s.m_solution.end());
					break;
				}
			}
		}
	}
	return flag;
}




//判断某一行是否全1
bool CExactCoverSolution::isFullOneRow(int rowIndex) const
{
	bool flag =true;
	for (int i=0;i<m_elementNum;++i)
		if (m_matrix[rowIndex][i]==0)
		{
			flag=false;
			break;
		}
	return flag;
}

int CExactCoverSolution::getFullOneRow() const
{
	bool flag =false;
	int rowIndex = -1;
	for (int i=0;i<m_subsetNum && !flag;++i)
	{
		if (isFullOneRow(i))
		{
			rowIndex = i;
			break;
		}
	}
	return rowIndex;
}


int CExactCoverSolution::GetColumnCount( int columnIndex ) const
{
	int sum=0;
	for(int i=0;i<m_subsetNum;++i)
		sum += m_matrix[i][columnIndex];
	
	return sum;
}

void CExactCoverSolution::getRowNos( const int c,vector<int>& rows,int value) const
{
	for (int i=0;i<m_subsetNum;++i)
		if (m_matrix[i][c]==value)
			rows.push_back(i);
}

void CExactCoverSolution::getColumnNos( const int r,vector<int>& columns,int value) const
{
	for (int i=0;i<m_elementNum;++i)
		if (m_matrix[r][i]==value)
				columns.push_back(i);
}

void CExactCoverSolution::getOtherRows( const int r,vector<int>& otherrows )const
{
	for(int i=0;i<m_subsetNum;++i)
	{
		bool flag=true;
		for(int j=0;j<m_elementNum;++j)
			if (m_matrix[i][j]==m_matrix[r][j] && m_matrix[r][j]==1)
			{
				flag=false;
				break;
			}
		if (flag)
			otherrows.push_back(i);
	}
}

void CExactCoverSolution::getNewNames( const vector<int>& rows,SUBSET_NAMES& names ) const
{
	for(int i=0;i<rows.size();++i)
		names.push_back(m_subsetNames[rows[i]]);
}

void CExactCoverSolution::getNewMatrix( const vector<int>& rows,const vector<int>& columns,MATRIX& matrix ) const
{
	matrix=MATRIX(rows.size(),vector<int>(columns.size()));
	for(int i=0;i<rows.size();++i)
		for(int j=0;j<columns.size();++j)
			matrix[i][j]=m_matrix[rows[i]][columns[j]];
}

void CExactCoverSolution::print(ostream&os ) const
{
	os << m_solution[0];
	for (int i=1;i<m_solution.size();++i)
	{
		os << ","<<m_solution[i];
	}
}

三、测试代码

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#include "ExactCoverSolution.h"

const int ELEMENT_NUM=7 ; //元素的个数
const int SUBSET_NUM=6;   //子集的个数

const int U[ELEMENT_NUM]={1,2,3,4,5,6,7};  //全集
const char NAMES[SUBSET_NUM]={'A','B','C','D','E','F'};  //各子集的名字
//0-1矩阵
const int Matrix[SUBSET_NUM][ELEMENT_NUM]={
	 {1,0,0,1,0,0,1}
	,{1,0,0,1,0,0,0}
	,{0,0,0,1,1,0,0}
	,{0,0,1,0,1,1,0}
	,{0,1,1,0,0,1,1}
	,{0,1,0,0,0,0,1}
};



int main(int argc,char* argv[])
{
	vector<vector<int> > M(SUBSET_NUM,vector<int>(ELEMENT_NUM));
	for (int i=0;i<SUBSET_NUM;++i)
		for (int j=0;j<ELEMENT_NUM;++j)
			M[i][j]=Matrix[i][j];

	FULL_SET values(U,U+ELEMENT_NUM);
	SUBSET_NAMES names(NAMES,NAMES+SUBSET_NUM);
	CExactCoverSolution s(M,names);
	
	if (s.search())
		s.print();
	cout<<endl;
	
	system("pause");
	return 0;
}

四、运行结果

B,D,F