题目描述
子集和问题的一个实例为〈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
参考代码
#include<stdio.h>
#include<stdlib.h>
#define N 10000
void fun(int,int,int );
int A[N],B[N],n,tag,flag=0;
int main()
{
int i,rest=0;
scanf("%d%d",&n,&tag);
for (i=0;i<n;i++)
{
scanf("%d",&A[i]);
B[i]=0;
rest=rest+A[i];
}
fun(0,0,rest);
if(flag==0)
printf("No Solution!");
return 0;
}
void fun(int d,int w,int rest)
{
int i;
if(rest+w<tag)
return;
rest=rest-A[d];
if(d==n+1)
return;
if(w>tag)
return;
if(w==tag)
{
flag=1;
for (i=0;i<d;i++)
{
if(B[i]==1&&i<d-1)
printf("%d ",A[i]);
if(B[i]==1&&i==d-1)
printf("%d",A[i]);
}
exit(-1);
}
for (i=0;i<2;i++)
{
if(i==0)
{
B[d]=1;
fun(d+1,w+A[d],rest);
}
if(i==1)
{
B[d]=0;
fun(d+1,w,rest);
}
}
}
解析
暂无