Chris_kxt
2018-05-01 15:55
采纳率: 71.4%
浏览 5.0k

C++语言编程 子集和问题(回溯法解) 注意用C++啊

设集合S={x1,x2,…,xn}是一个正整数集合,c是一个正整数,子集和问题判定是否存在S的一个子集S1,使S1中的元素之和为c。试设计一个解子集和问题的回溯法。
输入格式:

输入数据第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值。接下来的1行中,有n个正整数,表示集合S中的元素。 是子集和的目标值。接下来的1 行中,有n个正整数,表示集合S中的元素。
输出格式:

将子集和问题的解输出。当问题无解时,输出“No Solution!”。
输入样例:

在这里给出一组输入。例如:
5 10
2 2 6 5 4
输出样例:

在这里给出相应的输出。例如:
2 2 6

#include
using namespace std;

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • threenewbee 2018-05-01 15:58
    已采纳
     #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;//因为只需输出一组解,c++又没法结束整个程序,,怕超时到处加判断。。。(我智商低别理我)  
        for (r=1;r<=n;++r)  
          if (!b[r]&&c-a[r]>=0)  
          {  
            if (pd==1) return;  
            c-=a[r];//用c减去每个数,其实就是几个数之和等于c  
            d[dep]=a[r];//d是记录数组  
            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)//很重要的剪枝!!如果所有的数加起来都小于c,那么不可能有解。。之前有三组TLE,加了这一步竟然给蒙过了。。  
        {  
            printf("No solution!");  
            return 0;  
        }  
        memset(d,0,sizeof(d));  
        memset(b,0,sizeof(b));  
        pd=0;  
        dfs(1);  
        if (!pd) printf("No solution!");  
        return 0;  
    } 
    

    https://blog.csdn.net/clove_unique/article/details/47603677

    已采纳该答案
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题