perm.cpp

利用回溯法求解背包问题和全排列的算法

#include "iostream.h" 
class pailie
{
  friend   int pailieh(int);
  private:  bool kk(int i); 
	    	void backtrack(int);
	        int *x;
	        int  n;
			int sum;
};
bool pailie::kk(int n)
{  
    if (n!=1)
    {
		for (int i=1;i<n;i++)
	
	{
		if (x[i]==x[n])
		return false;	
	}
		return true;
    }
	 else
		return true;

}
void pailie::backtrack(int t)
{

	if (t>n)
	{   
		sum+=1;
		for (int i=1;i<=n;i++)
		{
			cout<<x[i];
		}
	    	cout<<endl;
	}
    for (int j=1;j<=n;j++)
    {
		x[t]=j;
		if(kk(t))
		{
	    	backtrack(t+1);
		}
    }
	
}
int pailieh(int n)
{	
	pailie A;
	A.n=n;
	A.sum=0;
	int *p=new int[n+1];
	for (int i=0;i<=n;i++)
	{
		p[i]=0;
	}
    A.x=p;
	A.backtrack(1);
	return A.sum;
  

}
void main()
{   

  cout<<pailieh(5);
 
}