5_1_1.cpp

子集和问题（非递归）

#include<stdio.h>
#define MMM 20
void main(void)
{
	int n,c,i,nc,k;                      //n为元素个数，c为给定的子集和，nc为当前的子集和
	int A[MMM],flag[MMM];
	int FLAG;
	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中得到集合的元素值
		flag[i]=0;
	}
	if((fp2=fopen("output.txt","w"))==NULL)
	{
		printf("file cannot be opened\n");
		//exit(1);
	}
	k=0;
	nc=0;
	FLAG=0;
	while(k>=0)                            //搜索子树，回溯法（深度遍历）
	{
		while(k<n&&nc+A[k]<c)             //进入左子树
		{
			nc=nc+A[k];
			flag[k]=1;
			k++;
		}
		if(k==n)                             //到达叶结点
		{
			k--;
			if(flag[k]=1)                   //叶结点被选择
			{
				for(;flag[k]==1;k--)        //剪枝回溯
					nc=nc-A[k];
				if(k<0)
				{
					fprintf(fp2,"No Solution!");   //所有元素之和都小于给定的子集和c
					break;
				}
			}
			for(;flag[k]==0;k--);                    //从右子树返回     
			if(k<0&&FLAG==0)                         //深度遍历结束
			{
				fprintf(fp2,"No Solution!");
				break;
			}
			if(k>=0)
			{
				flag[k]=0;                          //进入右子树
				nc=nc-A[k];
				k++;
			}
		}
		else
		{
			if(nc+A[k]==c)
			{
				flag[k]=1;
				for(i=0;i<=k;i++)
					if(flag[i]==1)
						fprintf(fp2,"%d ",A[i]);
				fprintf(fp2,"\n");
				FLAG=1;
			}
			flag[k]=0;         //进入右子树
			if(k==n-1)         //到达叶结点
			{
				for(k=n-1;flag[k]==0;k--);   //从右子树返回
				if(k<0&&FLAG==0)
				{
					fprintf(fp2,"No Solution!");
					break;
				}
				if(k>=0)
				{
					flag[k]=0;           //进入右子树
					nc=nc-A[k];
				}
			}
			if(k>=0)
				k++;
		}
	}
}