回朔法(定长的)动态.cpp

子集和问题.rar:这是我学算法设计时的总结,包括定长和不定长做法(也就是回朔法,剪枝限界),当然也包括穷举法.

#include <iostream>
using namespace std;

int * b;
int * x;
int n;
int sum;

int Sum();
int SumOfSub(int ,int ,int );
void Display(int *);
void init();

int main()
{

	int s=0,k=0,r;
	init();
	r=Sum();
//	cout<<r<<endl;
	SumOfSub(s,k,r);
	delete [] b;
	delete [] x;
	return 0;
}

void init()
{
		cout<<"Enter the length of the array :\n ";
	cin>>n;
	b=new int [n];
	x=new int [n];
	cout<<"Enter the members of the array : \n";
	for(int i=0 ; i<n ; ++i )
		cin>>b[i];
    cout<<"enter the sum:"<<endl;
	cin>>sum;
	for( i=0 ; i<n ; ++i )
		x[i]=0;

}

int Sum()
{
	int s=0;
	for(int i=0;i<n;i++)
	{
        s+=b[i];
	}
	return s;
}


int SumOfSub(int s,int k,int r)
{
	if(r<=0) return 0;
	x[k]=1;
	if(s+b[k]==sum)
	{
		Display(x);
	}
    if(s+b[k]+b[k+1]<=sum)
		SumOfSub(s+b[k],k+1,r-b[k]);
	x[k]=0;
	if(s+r-b[k]>=sum&&s+b[k+1]<=sum)
	{
		
		SumOfSub(s,k+1,r-b[k]);
	}
	return 0;
}

void Display(int *x)
{
	for(int i=0;i<n;i++)
	{
		if(x[i]==1)
			cout<<b[i]<<"\t";
	}
	cout<<endl;
}