子集和问题

8603 子集和问题
时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0
语言: not limited
描述
S是一个整数集合，S={x1,x2,...,xn}，c是一个整数。这里集合元素xi（1<=i<=n）和c都是整数，可能为负。子集和问题就是：判断是否存在S的一个子集S1，使得：
对S集合子集树采用深度优先的顺序进行搜索，子集树从上到下每层标示着S集合中每个从左到右元素“选”或者“不选”（左1右0）。试着用回溯算法设计解子集和问题。
输入格式
30
第一行2个数：正整数n和整数c。n表示S集合的大小，c是子集和的目标值，接下来一行中，有n个整数，表示集合S中的元素。
输出格式
将子集和问题的解输出，当无解时，输出"No Solution"（注意No Solution的大小写，空格，无标点）。
注意：依据S集合元素从左到右依次来画子集树，因此子集树唯一。若存在多种子集和问题的解时，只输出在这个唯一的子集树按深度优先方向遇到的第一个解，这样保证解的唯一性，利于评判。如：5 10 2 2 6 3 3 这里，2+2+6=10，2+2+3+3=10，但只输出2 2 6 如：5 10 2 2 3 3 6 只输出2 2 3 3 又如：5 -30 2 -2 6 -30 -3 只输出2 -2 -30
输入样例
5 10
2 2 6 5 4
输出样例
2 2 6
Hint
解空间树是“子集树”。
回溯法搜索，由于是深度优先的找，找到就退出算法。

------------------------------------------------------------------------

#include<iostream>
#include<malloc.h>
using namespace std;
//找到一个解立即退出所有递归
template<class Type>
class Loading{
    friend int* MaxLoading(Type [],Type,int,int*,int &);
private:
    void Backtrack(int i);
    int n,*x,flag;
    Type *w,sum,cw;
};
template<class Type>
void Loading<Type>::Backtrack(int i)
{
    if(i>n)
        return;
    if(flag) return;
    if(1){
        cw+=w[i];
        x[i]=1;
        if(cw==sum)
        {flag=1; return; }
        Backtrack(i+1);
        if(flag) return;//关键一步。。。
        cw-=w[i];
        x[i]=0;
    }
    Backtrack(i+1);
}
template<class Type>
int* MaxLoading(Type w[],Type sum,int n,int* x,int& flag)
{
    Loading<Type>X;
    X.w=w;
    X.x=x;
    X.sum=sum;
    X.n=n;
    X.cw=0;
    X.flag=0;
    X.Backtrack(1);
    flag=X.flag;
    return X.x;
}
int main()
{
    int n,sum,i;
    int *w,*x,flag=0;
    cin>>n>>sum;
    w=(int*)malloc((n+1)*sizeof(int));
    x=(int*)malloc((n+1)*sizeof(int));
    for(i=1;i<=n;i++)
    {cin>>w[i];
        x[i]=0;
    }
    x=MaxLoading(w,sum,n,x,flag);
    for(i=1;i<=n;i++)
    {
        if(x[i]==1)
            cout<<w[i]<<" ";
    }
    if(flag==0)
        cout<<"No Solution";
    return 0;
}
//用VC才能通过