子集和问题------基于dfs的回溯思想

来杯Sherry

发布于 2023-05-25 14:02:52

2660

发布于 2023-05-25 14:02:52

子集和问题 Description 子集和问题的一个实例为〈S,t〉。其中，S={ x1 ， x2 ，…，xn }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得：。试设计一个解子集和问题的回溯法。对于给定的正整数的集合S={ x1 ， x2 ，…，xn }和正整数c，计算S 的一个子集S1，使得：。 Input 输入数据的第1 行有2 个正整数n 和c（n≤10000，c≤10000000），n 表示S 的大小，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。 Output 将子集和问题的解输出。当问题无解时，输出“No Solution!”。

Sample Input 5 10 2 2 6 5 4 Output 2 2 6 Hint

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int pre[100010];
int vis[100010];
int tot =0;
int f =0;
int n,c;
void dfs(int p,int q)
{
    if(f||p>q)return;//已经到头、已搜索到答案

    vis[p] =1;
    tot+=a[p];

    if(tot == c)//已经搜索到答案
    {
        f =1;
        int j=0;
        for(int i=1; i<=p; i++)
        {
            if(j ==0 &&vis[i]){cout<<a[i];j++;}
            else if(vis[i])cout<<" "<<a[i];
        }
        cout<<endl;
        return;
    }

    if(tot+pre[n]-pre[p] <c) return;//已经没必要继续
    //go
    if(tot<c)dfs(p+1,n);
    //back
    tot-=a[p];
    vis[p] =0;
    dfs(p+1,n);


}
int main()
{

    cin>>n>>c;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        pre[i]+=pre[i-1]+a[i];
    }
    if(pre[n]<c)
    {
        cout<<"No Solution!"<<endl;
        return 0;
    }
    dfs(1,n);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-12-06，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs