子集和问题.cpp

子集和问题的一个实例（s

#include"fstream"
#include"iostream"
using namespace std;
#define N 1000   //数组的长度
int x[N];        //判断数组
int num;         //元素的个数

void subset_sum(int subset,int p[N],int s,int k,int sum){//前k-1个x[i]的值以定
	int i,j;
	x[k]=1;          //将第k个元素的取上   
	if(s+p[k]==subset){
		for(j=k+1;j<=num;j++){
			x[j]=0;  //将k以后的位置的值全置零
		}
		ofstream ofile;
		ofile.open("F:\\测试数据\\回溯法\\子集和问题\\out_subsum5.out");
		for(i=1;i<=num;i++)
			if(x[i]!=0)ofile<<p[i]<<" "; //根据判断数组将所选的元素输出的文件
		ofile<<endl;
		ofile.close();
		cout<<"任务完成！"<<endl;
		exit (0);                      //找到其中的一个解后即退出程序
	}
	if (s+p[k]+p[k+1]<=subset){        //如果当前取值的总和再加上后面的一项仍没有超过子集总和
		subset_sum(subset,p,s+p[k],k+1,sum-p[k]);//继续递归调用
	}
	if(s+sum-p[k]>=subset&&s+p[k+1]<=subset){
		x[k]=0;                        //将当前的第k个元素去掉
		subset_sum(subset,p,s,k+1,sum-p[k]);    //向后取一项后继续递归调用
	}
}


int main(){
	
	int subset;      //子集的和
	int p[N];        //读入的数组
	int i;
	int sum=0;       //数组元素的总和大小
	int s=0,k=1;     //s为目前取的数的总和大小，k为元素的序号

	ifstream ifile;
	ofstream ofile;
	ifile.open("F:\\测试数据\\回溯法\\子集和问题\\test\\subsum5.in");
	ifile>>num;      //读入数组元素的个数
	cout<<"num="<<num<<endl;
	ifile>>subset;   //读入子集的总和
	cout<<"subset="<<subset<<endl;
	cout<<"读入数组...";
	for(i=1;i<=num;i++){      //从下标为1的位置开始将元素装入p数组
		ifile>>p[i];
		sum=sum+p[i];         //计算数组元素的总和
	}
	cout<<endl;
	subset_sum(subset,p,s,k,sum);  //子集回溯函数
	return 0;
}