1759: 子集和问题

题目描述

子集和问题的一个实例为〈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);
        }
    }
}

解析

暂无