P1064-子集和问题

太过爱你忘了你带给我的痛 2022-07-11 11:25 238阅读 0赞

子集和问题  
描述 Description  
【问题描述】  
　　子集和问题的一个实例为〈S,t〉。其中，S=\{ x1， x2，…， xn\}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得子集S1和等于c。  
【编程任务】  
　　对于给定的正整数的集合S=\{ x1， x2，…， xn\}和正整数c，编程计算S 的一个子集S1，使得子集S1和等于c。  
【输入格式】  
　　由文件subsum.in提供输入数据。文件第1行有2个正整数n和c，n表示S的个数，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。  
【输出格式】  
程序运行结束时，将子集和问题的解输出到文件subsum.out中。当问题无解时，输出“No Solution!”。  
【输入样例】  
5 10  
2 2 6 5 4  
【输出样例】  
2 2 6

时间限制 Time Limitation  
各个测试点1s

这是一个**子集树**问题。如果用常规深搜递归解法的话，很显然时间复杂度太高

#include<iostream>
    #include<string.h>
    #include<stdlib.h>
    
    using namespace std;
    
    int total=0;
    int n,num[10001],k=0;
    bool map[10001];
    int arr[10001]={
       0};
    void print()
    {
        for (int i=1;i<=k;i++)
        {
            cout<<arr[i]<<" ";
        }
    }
    
    void search(int m,int h)
    {
         if(m==0) {
            print();total++;exit(0);
         }
         for(int i=1;i<=n;i++)
         {
            if(m-num[i]>=0&&map[i]==true&&i>h)
            {
                map[i]=false;
                 k++;
                arr[k]=num[i];
                search(m-num[i],i);
                arr[k]=0;
                k--;
                map[i]=true;
            }
         }
    }
    
    int main()
    {
    //时间复杂度为O（2^n）
        int m;
        cin>>n>>m;
        for (int i=1;i<=n;i++)cin>>num[i];
        memset(map,true,sizeof(map));
        search(m,0);
        if(total==0)cout<<"No Solution!";
    }

看到[http://blog.sina.com.cn/s/blog\_7865b083010100dd.html][http_blog.sina.com.cn_s_blog_7865b083010100dd.html]有一个非递归回溯算法:

> 但是很显然穷举所有子集的复杂度是2^n对于这个复杂度，计算机是很难承受的。到规模超过30的时候 ，已经几乎出不了结果了。所以采用一种更加快速的非递归回溯算法。它的思想是，从第一个元素开始，如果此时当前的元素不在集合内的话，将这个元素加到子集当中来（用visited数组标记） ，将sum加上这个元素的值。然后判断如果sum恰好为目标值c的话，就返回正值并且打印结果。如果sum > c 的话则舍弃当前这个元素，修改标记数组，并且将sum减去这个元素的值。只要还有元素没有判断就继续选择。直到第n个元素，如果第n个元素判断完还没有找到解的话，就回溯到上一次选择的那个点，将其从集合里面删除并从它后一个点继续重复前面的操作。如果回溯的时候回溯到了第一个元素之前的话呢，表示这个时候要么所有元素都加入到集合都不够，或者是所有的情况都找过了还是没有解决方案，这个时候返回无解。代码如下：
> 
>     #include<stdio.h>
>     
>     
>     #define MAX 10000
>     
>     int data[MAX] ;
>     bool v[MAX] ;
>     int n , c ;
>     bool traceback(int n){
>     int p = 0 ,sum = 0 ;
>     while(p>=0)
>     {
>     if(!v[p])
>     {
>     v[p] = true ;
>     sum += data[p] ;
>     if(c == sum)
>     return true ;
>     else if( c < sum)
>     {
>     v[p] = false ;
>     sum -=data[p] ;
>     }
>     p++ ;
>     }
>     if(p>=n)
>     {
>     while( v[p-1] )
>     {
>     p-- ;
>     v[p] = false ;
>     if(p<1) return false ;
>     }
>     while( !v[p-1])
>     {
>     p-- ;
>     if(p<1) return false ;
>     }
>     sum -= data[p-1] ;
>     v[p-1] = false ;
>     }
>     }
>     return false ;
>     }
>     int main(){
>     scanf("%d %d" , &n , &c) ;
>     for(int i = 0 ; i < n ; i++)
>     scanf("%d" , &data[i]) ;
>     if(traceback(n))
>     {
>     int first = 1 ;
>     for(int i = 0 ; i < n; i++)
>     if(v[i])
>     {
>     if(first)
>     first = 0 ;
>     else
>     printf(" ") ;
>     printf("%d" , data[i]) ;
>     }
>     printf("\n") ;
>     }
>     else
>     printf("No Solution!\n") ;
>     return 0 ;
>     }

对于这样的子集和问题，应该用dfs+子集树来完成。比如：  
[http://blog.csdn.net/qq\_27601815/article/details/53454017][http_blog.csdn.net_qq_27601815_article_details_53454017]

然而似乎是数据太水。我改了一下最上面的程序：

#include<iostream>
    #include<string.h>
    #include<stdlib.h>
    
    using namespace std;
    
    int total=0;
    int n,num[10001],k=0;
    bool map[10001];
    int arr[10001]={
       0};
    void print()
    {
        for (int i=1;i<=k;i++)
        {
            cout<<arr[i]<<" ";
        }
    }
    
    void search(int m,int h)
    {
         if(m==0) {
            print();total++;exit(0);
         }
         for(int i=1;i<=n;i++)
         {
            if(m-num[i]>=0&&map[i]==true&&i>h)
            {
                map[i]=false;
                 k++;
                arr[k]=num[i];
                search(m-num[i],i);
                arr[k]=0;
                k--;
                map[i]=true;
            }
         }
    }
    
    int main()
    {
        int m;
        cin>>n>>m;
        int total=0;
        for (int i=1;i<=n;i++)
        {
            cin>>num[i];
            total+=num[i];
        }
        if (total<m)
        {
            cout<<"No Solution!";
            return 0;
        }//剪枝1
        if (total==m)
        {
            for (int i=1;i<=n;i++)
            cout<<num[i]<<" ";
            return 0;
        }//剪枝2
        memset(map,true,sizeof(map));
    
        search(m,0);
        if(total==0)cout<<"No Solution!";
    }

其实也就加了一两个判断，然而在平台上测试的结果差距很大  
![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

[http_blog.sina.com.cn_s_blog_7865b083010100dd.html]: http://blog.sina.com.cn/s/blog_7865b083010100dd.html
[http_blog.csdn.net_qq_27601815_article_details_53454017]: http://blog.csdn.net/qq_27601815/article/details/53454017
[SouthEast]: /images/20220711/8c61e1117c8f4e62b4108ad17fdf2732.png
[SouthEast 1]: /images/20220711/ae064fd33e10481a87ee203772b2e538.png