子集和数的递归回溯.txt

都是自己编写的常用算法的事例,本人础作. 里面有:哈密尔顿环,皇后问题,图的着色问题,子集和数问题,树和等价问题,栈的各种用发等.

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

const int N = 6;                        //一共有N个数
int W[100] = { 0,5,10,12,13,15,18};     //这N个数的权值
const int M = 30;                       //和数
bool X[100];                            //标志是否选中W[i],i属于[1，N];


bool checkX( int sum,int n)
{
	if( n > N)
		return false;
	if(X[n] == 1 && sum + W[n] >M)
			return false;
	return true;
}

void show_result()
{
	int i = 0;
	cout<<endl<<"----------------------"<<endl;
	for( i=1; i<=N;i++)
		if(X[i] ==  1)
		cout<<W[i]<<"   ";

}
void select( int sum,int n)
{
	//sum前面n-1已求的和。现在判断x[n]取0还是取1
	int i = 0;
	for(i=0;i<=1;i++)
	{
		X[n] = i;
		if(checkX(sum,n)) //如果X[n]选择值i符合规则
		{
			if( X[n] == 1)
				sum += W[n];
			if( n == N && sum == M)
			{
				show_result();
			}
			else
				select( sum,n+1 );
		}
	}
}

void main()
{
	select(0,1);
	cout<<endl;
}