子集和问题

子集和问题

时间: 1ms        内存:64M

描述:


子集和问题的一个实例为〈S,t〉。其中,S={  x1 , x2 ,…,xn }是一个正整数的集合,c是一个正整数。子集和问题判定是否存在S的一个子集S1,使得:

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

对于给定的正整数的集合S={  x1 , x2 ,…,xn }和正整数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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注