`

8603 子集和问题

 
阅读更多

8603 子集和问题(必做)

时间限制:1000MS  内存限制:1000K
提交次数:795 通过次数:262

题型: 编程题   语言: C++;C;VC;JAVA

Description

S是一个整数集合,S={x1,x2,...,xn},c是一个整数。这里集合元素xi(1<=i<=n)和c都是整数,可能为负。

子集和问题就是:判断是否存在S的一个子集S1,使得:


对S集合子集树采用深度优先的顺序进行搜索,子集树从上到下每层标示着S集合中每个从左到右元素“选”或者“不选”(左1右0)。

试着用回溯算法设计解子集和问题。



 


输入格式

第一行2个数:正整数n和整数c。n表示S集合的大小(n<=100),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

 

//8603  左右子树01问题

#include <iostream>

#include <stdio.h>

using namespace std;

int n,c;

int a[1000]={0};

int b[1000]={0};

int found = 0;

int res = 0;

void backtrack(int deep){ // 子集树的搜索算法,根节点,i=1

    if(found) return;  // 已经找到就返回

    if(deep > n){

    if(res == c) {

              // 搜到n-1才设置标志

            found = 1;//found 是寻找标志,找到设为true

       }

        if(found){

            for(int i=0;i<n;i++)

        {

            if(b[i]==1)

            {

                cout << a[i] <<" " ;

            }

        }

        }

    }else{

         //无条件左子树

       res += a[deep];

       b[deep]=1;

       backtrack(deep+1);

       //搜索完左子树,无条件右子树

       res -= a[deep];

       b[deep]=0;

       backtrack(deep+1);

    }

}

int main()

{

    freopen("in.txt","r",stdin);

    cin >> n >> c;;

    for(int i=0;i<n;i++){

        cin >> a[i];

    }

   backtrack(0);

   if(!found)  //注意无解的情况

    cout<<"No Solution";

    return 0;

}

  • 大小: 13.8 KB
分享到:
评论

相关推荐

    8603子集和问题

    "8603子集和问题" 这是一道典型的搜索算法问题,特别是子集和问题。给定一个整数集合 S={x1,x2,...,xn} 和一个整数 c,目标是找到 S 的一个子集 S1,使得 S1 的元素之和等于 c。 在这里,我们可以使用回溯算法来...

    子集和问题

    8603 子集和问题 时间限制:1000MS 内存限制:1000K 提交次数:795 通过次数:262 题型: 编程题 语言: 无限制 Description S是一个整数集合,S={x1,x2,...,xn},c是一个整数。这里集合元素xi(1)和c都是整数,可能...

    子集和问题子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,...,xn}是一个正整数的集合,c

    子集和问题 Description 子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,...,xn}是一个正整数的集合,c 是一个正整数。子集和问题判定是否存在S的一个子集S1,使得x∈S1,∑x=c. 试设计一个解子集和问题的回溯法...

    回溯法求解子集和问题

    回溯法是一种强大的算法策略,常用于解决组合优化问题,如子集和问题。这个问题的目标是从给定的一组整数中找出所有可能的子集,使得这些子集的元素和等于一个特定的目标值。在本案例中,我们将深入探讨如何使用回溯...

    子集和问题(算法设计,acm)

    ### 子集和问题解析与实现 #### 一、子集和问题介绍 子集和问题(SubSet Sum Problem)是一个经典的计算机科学问题,在算法设计、数据结构、甚至密码学等领域都有广泛的应用。该问题的基本形式是:给定一组整数和一...

    5-1+_子集和问题_

    子集和问题的一个实例为?St?〈St〉。其中,S={x1,x2,…,xn}S={x1,x2,…,xn}是一个正整数的集合,c是一个正整数。子集和问题判定是否存在 S 的一个子集 S1,使得 ∑x∈S1x=c ∑x∈S1x=c。试设计一个解子集和...

    算法设计实现题子集和问题c实现

    5-1 子集和问题 问题描述:子集和问题的一个实例为,t&gt;。其中,S={x1,x2,...,xn}是一个正整数的集合,c是一个正整数 。 子集和问题判定是否存在S 的一个子集S1,使得子集里的元素之和为c 试设计一个解子集和问题的...

    算法设计与分析-子集和问题

    ### 算法设计与分析:子集和问题 #### 问题定义 子集和问题是一种经典的计算机科学问题,属于NP完全问题。该问题的基本形式是:给定一个正整数集合\( S=\{x_1,x_2,…,x_n\} \)和一个正整数\( c \),询问是否存在...

    完全多项式时间近似算法(子集和问题)

    子集和。近似算法能够获得近似值和近似解,并且是一种完全多项式时间近似方案。 包括指数时间算法、修整算法、近似算法,可以获得近似值和近似解

    子集和问题C++.txt

    子集和问题C++.txt

    子集和问题代码

    算法分析课程作业,C语言编写,可能需要用input.txt输入,子集和问题代码

    子集打印问题~新奇算法

    本文将深入探讨一个经典问题——打印子集问题,并介绍一种新奇的算法解决策略。"子集打印问题"通常指的是从一个给定的集合中找出所有可能的子集,并将其打印出来。这个问题在计算机科学中具有重要的理论价值,因为它...

    子集和数 C语言求解

    在编程领域,子集和数问题是一个经典的算法问题,它要求我们从给定的数集中找出所有可能的子集,使得这些子集的元素之和等于一个特定的目标值。在这个问题中,我们使用C语言来解决,同时标签指出了解决这个问题的一...

    子集和数问题(回溯法)

    给定N个数,和一个整数M,判定是否可以从N个数中取出若干个数,使它们的和等于M。输出:YES或者NO。把N个数看成一个集合,问题就是从这个集合中选出一个子集,使这个子集满足和是M

Global site tag (gtag.js) - Google Analytics