子集和问题

子集和问题

时间： 1ms        内存：64M

描述：

子集和问题的一个实例为〈S,t〉。其中，S={  x₁ ， x₂ ，…，x_n }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得：

。

试设计一个解子集和问题的回溯法。

对于给定的正整数的集合S={  x₁ ， x₂ ，…，x_n }和正整数c，计算S 的一个子集S1，使得：

。

输入：

输入数据的第1 行有2 个正整数n 和c（n≤10000，c≤10000000），n 表示S 的大小，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出：

将子集和问题的解输出。当问题无解时，输出“No Solution!”。

示例输入：

5 10
2 2 6 5 4

示例输出：

2 2 6

提示：

参考答案（内存最优[1168]）：

#include<cstdio>
int a[10005];
int n,tar;
int vis[10005];
int flag,now; 
void print()
{
	for(int i=0;i<n;i++)
	   if(vis[i])
	   printf("%d ",a[i]);
}
void dfs(int k)
{
	if(flag)
	return;
	for(int i=0;i<=n;i++)
	{
		if(vis[i]==0&&now+a[i]<=tar)
		{
			if(flag)
           	return;
           	now+=a[i];
           	vis[i]=1;
           	if(now==tar)
           	{
           		flag=1;
           		print();
           		return;
			}
			else dfs(k+1);
			now-=a[i];
			vis[i]=0;
		}
	}
}
int main()
{
	long long int sum=0,t=0;;
	scanf("%d %d",&n,&tar);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	if(sum<tar)
	{
		printf("No Solution!");
		return 0;
	}
	dfs(0);
	if(flag==0)
	printf("No Solution!");
	return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,c,a[10000],b[10000],d[10000],i,sum=0;
bool pd;

void print(int dep)
{
	int j;
	for (j=1;j<=dep;++j)
	  printf("%d ",d[j]);
	printf("\n");
	return;
}

void dfs(int dep)
{
	int r;
	if (pd==1) return;
	for (r=1;r<=n;++r)
	  if (!b[r]&&c-a[r]>=0)
	  {
	  	if (pd==1) return;
	  	c-=a[r];
	  	d[dep]=a[r];
	  	b[r]=1;
	  	if (c==0)
	  	{
	  		if (pd==0)
	  		  print(dep);
	  		pd=1;
	  		return;
	  	}
	  	else dfs(dep+1);
	  	if (pd==1) return;
	  	c+=a[r];
	  	b[r]=0;
	  }
}

int main()
{
	scanf("%d%d",&n,&c);
	for (i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	if (sum<c)
	{
		printf("No Solution!\n");
		return 0;
	}
	memset(d,0,sizeof(d));
	memset(b,0,sizeof(b));
	pd=0;
	dfs(1);
	if (!pd) printf("No Solution!\n");
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。