Chris_kxt 2018-05-01 07:55 采纳率: 100%
浏览 5710
已采纳

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;

  • 写回答

2条回答 默认 最新

  • threenewbee 2018-05-01 07: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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 损失匹配问题,求解答
  • ¥15 3500常用汉字书法体检测数据集下载
  • ¥15 odoo17在制造模块或采购模块良品与次品如何分流和在质检模块下如何开发
  • ¥15 Qt音乐播放器的音乐文件相对路径怎么写
  • ¥15 VB.NET利用摄像头拍照的程序
  • ¥15 linux下vscode设置不了字连体
  • ¥20 游戏mod是如何制作的
  • ¥15 关于#hadoop#的问题:按照老师上课讲的步骤写的
  • ¥20 有人会用这个工具箱吗 付fei咨询
  • ¥30 成都市武侯区住宅小区兴趣点