Advertisement

子集与问题

阅读量:

问题描述
子集和问题的一个具体实例可表示为〈S,t〉。其中,S={x1,x2,…,xn}是由若干正整数组成的集合,c为一个正整数。该问题的核心在于判断是否存在S的一个子集S1,满足以下条件:

请设计一种基于回溯法的算法以解决子集和问题。
对于给定的正整数集合S={x1,x2,…,xn}以及目标值c,计算出一个满足条件的子集S1,使得:

输入
输入数据的第一行包含两个正整数n和c(n≤10000,c≤10000000),其中n表示集合S中元素的数量,c为所求子集和的目标值。紧接着的一行包含n个正整数,用于表示集合S中的各个元素。
输出
输出满足条件的子集和问题解。若不存在符合条件的解,则输出“No Solution!”。

样例输入
5 10
2 2 6 5 4
样例输出
2 2 6

此题后台测试数据数量较少… 存在一些问题存在问题存在问题

复制代码
    #include <bits/stdc++.h>
    using namespace std;
    
    int a[10010];
    int n, c;
    bool v[10010];
    
    bool trace()
    {
    int p = 0, sum = 0;
    
    while(p 

全部评论 (0)

还没有任何评论哟~