1764 子集和问题

柔光的暖阳◎ 2022-04-24 10:56 226阅读 0赞

### 子集和问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

子集和问题的一个实例为〈S,t〉。其中，S=\{ x1 ， x2 ，…，xn \}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得：  
![1764.png][]。  
试设计一个解子集和问题的回溯法。  
对于给定的正整数的集合S=\{ x1 ， x2 ，…，xn \}和正整数c，计算S 的一个子集S1，使得：  
![1764.png][]。

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

Sample Output

2 2 6

没有完全理解，先贴上来吧 QAQ

#include <bits/stdc++.h>
    using namespace std;
    
    int val=0,sum=0,n,c;          //n 表示S 的大小，c是子集和的目标值
    int s[10100],a[10100];
    
    bool find(int k){
      if (val == c)
        return true;
      if(k > n)
        return false;
    
      sum -=  s[k];
      if (val + s[k] <= c) {
        a[k] = 1;
        val += s[k];
        if(find(k+1))
          return true;
        val -= s[k];
      }
      if(val + sum >= c){
        a[k] = 0;
        if(find(k+1))
          return true;
      }
      sum +=  s[k];
      return false;
    }
    
    int main(){
      cin >> n >> c;
      for(int i = 1; i <= n; i++){
        std::cin >> s[i];
        sum += s[i];
      }
      memset(a,0,10100);
      if(find(1)){
        for(int i = 1; i <= n; i++){
          if (a[i])
            std::cout << s[i] << " ";
        }
        std::cout << '\n';
      }
      else
        std::cout << "No Solution!" << '\n';
    }

[1764.png]: http://acm.sdut.edu.cn/image/1764.png

发表评论取消回复

表情：

评论列表（有 0 条评论，226人围观）

还没有评论，来说两句吧...

相关阅读

相关算法__子集和问题

子集和问题就是　给出一个数组arr和一个值sum　　输出满足和为sum的arr的子集子集和问题从某种程度上来说其实就是 01背包问题的子问题还是取一种情况不取是另

╰半夏微凉°/ 2023年10月07日 12:33/ 0 赞/ 31 阅读

相关子集和

问题描述：子集和问题的一个实例为<S,c>。其中S=\{x1,x2,…,xn\}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中所有元

太过爱你忘了你带给我的痛/ 2022年08月05日 02:59/ 0 赞/ 253 阅读

相关 P1064-子集和问题

子集和问题描述 Description 【问题描述】　　子集和问题的一个实例为〈S,t〉。其中，S=\{ x1， x2，…， xn\}是一个正整数的集合，c是一

太过爱你忘了你带给我的痛/ 2022年07月11日 11:25/ 0 赞/ 258 阅读

相关【lintcode】子集问题

这里的子集问题是指给定一个列表求它的所有不重复子集的问题。这个问题分为两类：一类是所给列表包含重复元素，另一类是所给列表不含重复元素。分别对应lintcode中17和18题。

梦里梦外;/ 2022年05月24日 08:45/ 0 赞/ 243 阅读

相关 1764 子集和问题

子集和问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 子集和问题的一个实例为〈S

柔光的暖阳◎/ 2022年04月24日 10:56/ 0 赞/ 227 阅读

相关子集和问题

子集和问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 子集和问题的一个实例为〈S

我就是我/ 2022年04月24日 09:58/ 0 赞/ 259 阅读

相关子集和问题

子集和问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 子集和问题的一个实例为〈S

た入场券/ 2022年02月16日 14:49/ 0 赞/ 270 阅读

相关子集和问题：按给定子集和完全划分集合

需求是这样的：有44个数字A1-A44：1420, 1198, 493, 300, 3006, 881, 2450, 1372, 3643, 1350, 598, 615

柔情只为你懂/ 2022年02月04日 16:09/ 0 赞/ 285 阅读

相关子集和问题：按给定的子集和从集合找出满足的所有子集

import java.util.Scanner; public class test { static int sum=0;

布满荆棘的人生/ 2022年02月02日 04:45/ 0 赞/ 266 阅读

相关子集生成问题

/include<cstdio> include<algorithm> using namespace std; void print_subs

分手后的思念是犯贱/ 2021年09月30日 13:56/ 0 赞/ 326 阅读