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;
}
相关推荐
"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都是整数,可能...
子集和问题 Description 子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,...,xn}是一个正整数的集合,c 是一个正整数。子集和问题判定是否存在S的一个子集S1,使得x∈S1,∑x=c. 试设计一个解子集和问题的回溯法...
回溯法是一种强大的算法策略,常用于解决组合优化问题,如子集和问题。这个问题的目标是从给定的一组整数中找出所有可能的子集,使得这些子集的元素和等于一个特定的目标值。在本案例中,我们将深入探讨如何使用回溯...
### 子集和问题解析与实现 #### 一、子集和问题介绍 子集和问题(SubSet Sum Problem)是一个经典的计算机科学问题,在算法设计、数据结构、甚至密码学等领域都有广泛的应用。该问题的基本形式是:给定一组整数和一...
子集和问题的一个实例为?St?〈St〉。其中,S={x1,x2,…,xn}S={x1,x2,…,xn}是一个正整数的集合,c是一个正整数。子集和问题判定是否存在 S 的一个子集 S1,使得 ∑x∈S1x=c ∑x∈S1x=c。试设计一个解子集和...
5-1 子集和问题 问题描述:子集和问题的一个实例为,t>。其中,S={x1,x2,...,xn}是一个正整数的集合,c是一个正整数 。 子集和问题判定是否存在S 的一个子集S1,使得子集里的元素之和为c 试设计一个解子集和问题的...
### 算法设计与分析:子集和问题 #### 问题定义 子集和问题是一种经典的计算机科学问题,属于NP完全问题。该问题的基本形式是:给定一个正整数集合\( S=\{x_1,x_2,…,x_n\} \)和一个正整数\( c \),询问是否存在...
子集和。近似算法能够获得近似值和近似解,并且是一种完全多项式时间近似方案。 包括指数时间算法、修整算法、近似算法,可以获得近似值和近似解
子集和问题C++.txt
算法分析课程作业,C语言编写,可能需要用input.txt输入,子集和问题代码
本文将深入探讨一个经典问题——打印子集问题,并介绍一种新奇的算法解决策略。"子集打印问题"通常指的是从一个给定的集合中找出所有可能的子集,并将其打印出来。这个问题在计算机科学中具有重要的理论价值,因为它...
在编程领域,子集和数问题是一个经典的算法问题,它要求我们从给定的数集中找出所有可能的子集,使得这些子集的元素之和等于一个特定的目标值。在这个问题中,我们使用C语言来解决,同时标签指出了解决这个问题的一...
给定N个数,和一个整数M,判定是否可以从N个数中取出若干个数,使它们的和等于M。输出:YES或者NO。把N个数看成一个集合,问题就是从这个集合中选出一个子集,使这个子集满足和是M