邮票问题（用递归回溯）.txt

来自「都是自己编写的常用算法的事例,本人础作. 里面有:哈密尔顿环,皇后问题,图的着」· 文本 代码 · 共 62 行

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

const int N = 6;                        //一共有N个数
int W[100] = { 0,5,10,12,14,18,20};     //这N个数的权值
const int MAXNUM = 6;                   //最多允许的邮票数目
const int M = 30;                       //所求的和数
int X[MAXNUM+1];                        //记录W的下标，解向量    


bool checkX( int sum,int n)
{
	int index = X[n];
	if( sum + W[index] > M )            //如果比M要大则不不符合规则
		return false;
	return true;
}

void show_result(int n)
{
	int i = 0;
	cout<<endl<<"----------------------"<<endl;
	int index; 
	for( i=1; i<=n;i++)
	{
		index = X[i];
        cout<<W[index]<<"    ";
	}
    cout<<endl;
}
void select( int sum,int n)
{
	//sum前面n-1已求的和。现在判断x[n]取哪个值的下标
	int i = 1;
	int sumA[N+1] ={0};  //记录当x[n]取的值而导致的和值增加。

	for(i=1;i<=N;i++)
	{
		X[n] = i;          
		if(checkX(sum,n)) //如果X[n]选择i下标符合规则
		{
			sumA[i] = sum + W[i];
			if( sumA[i] == M )
			{
				show_result(n);
			}
			else if( n < MAXNUM)
			{
				cout<<"select("<< sumA[i]<<","<<n+1<<")"<<endl;
				select( sumA[i],n+1 );
			}
			//else：什么都不做。
		}
	}
}

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