邮票问题的一部份（编得一团糟）.txt

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

/邮票问题的一小部分，but i have messed it up。要重新编写过！
#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;

int kindNum = 4;
vector<int> moneyPaper(100);  //0号下标未用
int maxPermission = 5;
vector<int>  x(100); //存放答案序列(存的是moneyPaper的下标而不是面值)，最多由kindNum个元素组成


bool NextValueByRule( int &currSum,int sum,int k)
{
//注意，在要引起回溯的时候，要把x[k]重新设置为0
 int i; 
 if( k == maxPermission)
  {
	  for( i = 1; i <= kindNum;i++)
	  {
		  if(currSum + moneyPaper.at(i) == sum)
		  {
			  x[k] = i;
			  currSum = sum; 			 
			  return 1;    //答案已经找到。
		  }
	  }
	  x[maxPermission]=0;
	   return 0;       //需要回溯
  }
 else
 {
	 x[k] = div(x[k]+1,kindNum+1).rem;
	 if( x[k]==0) //需要回溯
	 {
		 currSum -=  moneyPaper.at(kindNum);
		 return 0;
	 }
	 else
	 {
		 currSum +=  moneyPaper.at(x[k]);
		 currSum -=  moneyPaper.at(x[k]-1);
		 if( currSum > sum)
		 {
			 currSum -=  moneyPaper.at(x[k]);
			 x[k] = 0;
			 return 0;
			 
		 }
	    return 1;
	 }
 }
}
void OutPut( int k)
{
  int i;
  cout<<"--------------------------"<<endl;
  for( i = 1 ; i <= k; i++ )
  {
	  cout<<"  "<< moneyPaper.at(x[i]);
  }
  cout<<endl;
}

void StampCombination()
{
	//邮票问题，有kindNum种面值的钞票，最多允许5张，问能否组合成money。
	int sum = 64;
    int currSum = 0;
	int k = 1;
	int num =1;

	while( k > 0)         //当k = 0 时结束算法
	{
		
		if(NextValueByRule(currSum,sum,k))//如果第k个数据存在有效的值
		{
			if( currSum == sum)          //这个算法只能求出一个解。
			{
				OutPut(k);
				break;                          
			}
			else
				k++;
		}
		else
		{
			k--;
		}
	}//while
}

void main()
{
	 moneyPaper.at(1) = 1;
	 moneyPaper.at(2) = 4;
	 moneyPaper.at(3) = 12;
	 moneyPaper.at(4) = 21;
     StampCombination();
}