子集和问题（回溯法）_子集和问题回溯法_wuthering_wind的博客-程序员资料

1.问题描述：

设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法。输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。将子集和问题的解输出。当问题无解时，输出“No Solution!”。

2.解决问题的思路：

A.用回溯法解决问题，首先我们需要判断应当使用子集树还是排列树。当然对于这个问题，应该使用子集树。

B.然后我们就可以套入子集数的模版

C.当然我们也需要根据实际情况进行相应的调整。用适当的Constraint（）和Bound（）函数进行递归条件的控制。

3.代码示例：

#include<stdio.h> 
# define M 100 
 int n;//正整数集合成员数量
 int all;// 正整数子集的和
 int arr[M];//正整数集合
 int x[M]; //记录子集成员
 int mark=0; 

int Constrain(int t){
 int i;
 int sum=0; 
 for(i=0;i<=t;i++) {//子集求和
 if(x[i]==1) sum+=arr[i]; 
 } 
 if(sum==all){
  printf("找到最优解"); 
  for(i=0;i<=t;i++) {  //把最优解打印出来
 if(x[i]==1) printf("%d ",arr[i]); 
 } 
 mark=1; //只要找到最优解，那么问题就结束
 } 
}

int  Bound(int t){//检测有没有到达叶子节点
 if(t<n) 
  return 1;
 else return 0; 
}
int  Backtrack(int t){//典型的子集树，不再解释
 
 int i;
 
 if(t<n){
  for(i=0;i<=1;i++){
  x[t]=i;
  if(Constrain(t)&&Bound(t)){
  if(mark==1)return 0; 
   Backtrack(t+1);
  }
 } 
} 
}
 
int main(){
 int i; 
 scanf("%d %d",&n,&all); 
 
 for(i=0;i<n;i++) {//给正整数集合赋值
 scanf("%d",&arr[i]); 
 } 
 
 for(i=0;i<n;i++) {//记录子集成员，一开始为空，也就是标记集合为全为0
    x[i]=0; 
 } 
 
 Backtrack( 0);
  
}

4.需要注意的一点是，对于子集和问题，找到问题的一个解即可。因此找到解程序就结束。如果是其他问题，可以根据情况作调整。

本文链接：https://blog.csdn.net/wuthering_wind/article/details/80473686

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Python+Django连接mysql 自动创建model_python django mysql 自动生成模型_爪哇天河的博客-程序员资料

python+django对数据库的支持是非常多的。可以使用默认的sqlite数据库。

RFSoC全面解析（二）——ZCU111开发板介绍_lightninghenry的博客-程序员资料

话不多说，先上开发板实物图，图片看着显小，实物和A4纸差不多大。全套东西如下：上图右下角有个射频接口板，是和ZCU111的RFMC接口对插的。插好后实物图如下：开发板的说明文档见UG1271，可从XILINX官网下载。...

OpenShift 4 - Fedora CoreOS (6) - 用rpm-ostree安装软件、升级回滚CoreOS_dawnsky.liu的博客-程序员资料

文章目录什么是 rpm-ostree更新操作系统自动更新 rpm-ostree手动更新 rpm-ostree比较更新前后差别回滚系统更新切换当前的rpm-ostree版本安装软件删除软件参考什么是 rpm-ostree在 RHCOS/FCOS 中没提供像 RHEL/CentOS 的YUM工具，RHCOS/FCOS 使用了 rpm-ostree 来实现基于“Transaction-事务”的软件安装升级。不像 YUM 那样是单个升级更新软件包，rpm-ostree 是将升级更新作为一个原子单元进行的。类似“

如何成为一个合格的java程序员？_nqzwaityou的博客-程序员资料

如何成为一个合格的java程序员? 1、语法：必须比较熟悉，在写代码的时候IDE的编辑器对某一行报错应该能够根据报错信息知道是什么样的语法错误并且知道任何修正。　　2、命令：必须熟悉JDK带的一些常用命令及其常用选项，命令至少需要熟悉：appletviewer、HtmlConverter、jar、java、javac、javadoc、javap、javaw、native2asc

服务器桌面监控,GitHub - 373137461/wallpaper_monitor: 适用于 Wallpaper Engine 等桌面壁纸软件的服务器状态监控软件，使用 PHP 开发..._瓜子仁呀的博客-程序员资料

Wallpaper Monitor一款为 Wallpaper Engine 等壁纸软件设计的服务器监控小插件，使用 PHP 编写使用需要 Linux 服务器，并且安装了 Web 服务器 + PHP 5.6 以上，可以是 Nginx、Apache 等。注意：默认的壁纸包含不适合未成年人浏览的内容，有需要请自行替换。壁纸替换方法：修改 index.php ，找到第 174 行，替换 url 中的链接为...

RPA认证 Developer UIPath Certificate,细说uipath认证学习，Online Quiz和Practical Exam项目详解_u010369735的博客-程序员资料

UIPath，RPA里算是比较简单易操作的一款软件了，因为公司业务的需要，代理uipath以及部署业务，所以接触到了uipath。从开始到最终做到企业项目部署，大概用了两个月的时间，收获不少。自己之前是做过后端开发，前端以及手机端软件自动化的相关开发工作（触动sprite…），所以学习起来挺快的。最终花了两周多的时间，阅读了官方的文档，uiapth官方的学院，以及第三方一些文档，完成了整个uipa...

随便推点

maven tomcat插件的作用_q42368773的博客-程序员资料

我们现在有这样一个需求，在eclipse中有两个子模块的mave war包，如果我们想以不同的端口和上下文启动两个war包，就得在eclipse中配置两个server分别部署连个war。使用mave插件后，可以直接使用命令来启动工程，配置方法如下： <build> <plugins>  <pl...

开发环境上云，打造五星级开发体验_it研发环境上云案例_腾云 CODING的博客-程序员资料

本文作者：王振威 - CODING 研发总监全文约 5000+ 字，预计阅读时间 20 分钟云是从传统 IDC 机房演进而来，一开始云的定位只是为了解决数据中心的弹性计算，高可用等问题。可以说，公有云让成千上万家企业灵活地按需租用数据中心资源成为可能，同时在推动社会数字化发展上起到了关键作用。但简简单单的把云理解为资源的按需租用太狭隘了，随着云技术和行业标准的发展，云原生的概念开始出现。云原生变革了传统应用，传统的应用可以运行在本地开发电脑上，到真正正式提供生产服务才被云以弹性的，高可用的资源提供.