5_1_3.cpp

子集和问题（分支界限法）

#include"stdio.h"
#define MMM 20
#define MMMM 10000

void main(void)
{
	int n,c,i,nc,k,j,m;                      //n为元素个数，c为给定的子集和，nc为当前的子集和
	int A[MMM],C[MMM],flag[MMMM],B[MMMM],parent[MMMM];
	FILE *fp1,*fp2;
	if((fp1=fopen("input.txt","r"))==NULL)
	{
		printf("file cannot be opened\n");
		//exit(1);
	}
	fscanf(fp1,"%d %d",&n,&c);           //从文件input.txt中得到集合的元素个数n，给定的子集和c
	for(i=0;i<n;i++)
		fscanf(fp1,"%d",&A[i]);          //从文件input.txt中得到集合的元素值
	if((fp2=fopen("output.txt","w"))==NULL)
	{
		printf("file cannot be opened\n");
		//exit(1);
	}
	k=0;
	nc=0;
	i=0;
	j=0;
	flag[i]=-1;
	parent[i]=-1;
	B[i++]=-1;
	while(k<n)
	{
		if(nc+A[k]<=c)
		{			
			flag[i]=1;
			parent[i]=j-1;
			B[i++]=nc+A[k];
			if(nc+A[k]==c)
				break;
		}
		flag[i]=0;
		parent[i]=j-1;
		B[i++]=nc;			
		nc=B[j++];
		if(nc==-1)
		{
			flag[i]=-1;
			parent[i]=j-1;
			B[i++]=-1;
			nc=B[j++];
			k++;
		}
	}
	/*for(m=0;m<i;m++)
	{
		printf("%5d%5d%5d\n",flag[m],B[m],parent[m]);
	}*/
	if(k<n)
	{
		i--;
		j=0;
		for(m=k;m>=0;m--)
		{
			if(flag[i]==1)
				C[j]=A[m];
			else
				C[j]=0;
			j++;
			i=parent[i];
		}
		for(m=j-1;m>=0;m--)
			if(C[m]!=0)
				fprintf(fp2,"%d ",C[m]);
	}
	else 
		fprintf(fp2,"No Solution!");

}