zxh5.cpp

本程序实现的是一个对于一个给定的数字集合,再给一个数字限制,求得这个集合的所有子集合,使子集合的各个元素之和为给定的数字限制,如果没有这样的子集合,则输入为空! 程序本身运用的是回朔算法,但

#include<stdio.h>
#define  N  5
int x[N+1],w[N+1];
int Search_R(int C)
{
	int i=1,j;
    int Bestw=0;
	int cw=0;
	int r=0;
   for(j=1;j<=N;j++)
   {
	   r+=w[j];
       x[j]=0;
   }
	
	while(1)
	{
		while(i<=N&&cw+w[i]<=C)
		{
			if(cw+w[i]==C)
			{	
		    cw+=w[i];
			x[i]=1;
			r-=w[i];
			i++;
            for(j=1;j<=N;j++)
			{
				if(x[j]==1)
				 printf("  %d ",w[j]);
            }
				 printf("\n");
				 printf("对应的布尔向量x[N]为:   ");
              for(j=1;j<=N;j++)
			     printf("  %d ",x[j]);
			printf("\n\n");
			}
			else
			{
            cw+=w[i];
			x[i]=1;
			r-=w[i];
			i++;
			}
		}
		if(i>N)
			Bestw=cw;
		else
		{
			x[i]=0;
		    r-=w[i];
			i++;
		}


		while(cw+r<=Bestw)
		{
			if(cw+r==Bestw&&r!=0)
				break;
			else 
			{
				i=i-1;
				while(i>0&&x[i]==0)
				{
					r+=w[i];
					i--;

				}
				if(i==0)
				{
					if(Bestw!=C)
					   printf("没有这样的集合!\n");
					return 0;
				}
					x[i]=0;
				cw-=w[i];
				i++;

			}
		
		}
	}
	
}
int main()
{
	int i,C;
	printf("请输入一个数字集合(集合的大小为N):\n");
	for(i=1;i<=N;i++)
		scanf("%d",&w[i]);
	printf("请输入一个子集合的各元素之和的数字\n");
    scanf("%d",&C);
	printf("这样的子集合总共为:\n\n");
    Search_R(C);
	return 0;
}