回朔法(定长的).cpp

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

#include <iostream>
using namespace std;

const int MAX=11;
const int b[MAX]={1,2,3,4,5,8,11,23,45};
int x[MAX]={0};
int sum;

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

int main()
{
    cout<<"enter the sum:"<<endl;
	cin>>sum;
	int s=0,k=0,r;
	r=Sum();
//	cout<<r<<endl;
	SumOfSub(s,k,r);
	system("pause");
	return 0;
}

int Sum()
{
	int s=0;
	for(int i=0;i<MAX;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<MAX;i++)
	{
		if(x[i]==1)
			cout<<b[i]<<"\t";
	}
	cout<<endl;
}