算法__子集和问题

╰半夏微凉° 2023-10-07 12:33 13阅读 0赞

子集和问题就是　给出一个数组arr和一个值sum　　输出满足和为sum的arr的子集

子集和问题 从某种程度上来说 其实就是 01背包问题的 子问题 还是取一种情况 不取是另外一种情况 然后 用回溯法 构建出一棵树来遍历一下

#include <iostream>
 #include <cstring>
 
 using namespace std;
 
 const int N = 1000; 
 
 int arr[N]; // 存储几何元素
 bool vis[N]; // 存储集合状态
 int valSum; //当前和
 
 void slove(int i , int n , int m){
 
 
 	//超出范围
 	if(i > n){
 
 		return ;
 	}
 
 	// 取数
 	vis[i] = true;
 	valSum += arr[i];
 
 
 	//满足 输出
 	if(valSum == m){
 
 		printf("{");
 		for(int j = 0; j <= i; j++){
 
 			if(vis[j] == true){
 
 				printf("%d,",arr[j]);
 			}
 		}
 		printf("}\n");
 	}else if(valSum < m){
 // 不足 继续取数
 		slove(i+1,n,m);
 	} 
 
 
 	//回溯
 	vis[i] = false;
 	valSum -= arr[i];
 
 	slove(i+1,n,m);
 	return ;
 }
 
 int main(int argc, char const *argv[])
 {
 
 	int num,sum;// num 数组长度 sum 目标和
 	scanf("%d%d",&num,&sum);
 	for(int i = 0; i < num ;i++){
 
 		scanf("%d",&arr[i]);
 	}
 
 	slove(0,num,sum);
 	return 0;
 }

子集和数问题

### 问题描述 ###

已知(w1, w2, …, wn)和M，均为正数。要求找出wi的和数等于M的所有子集。

例如：若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31，则满足要求的子集是(11,13,7)和(24,7).

### 分析 ###

子集和数问题解的一种表示方法

*  解由n-元组(x1, x2, …, xn)表示;
 *  显式约束条件xi∈\{0,1\} ，1≤i≤n，如果没有选择Wi，则xi=0；如果选择了Wi，则xi=1。于是上面的解可以表示为(1，1，0，1)和(0,0,1,1);
 *  隐式约束条件(xi× wi)的和数为M
 *  解空间的大小为2n个元组

### 子集和数的递归回溯算法 ###

//找W（1：n）中和数为M的所有子集。进入此过程时X(1),…,X(k-1)的值已确定。W(j)按非降次序排列。

<table> 
 <tbody> 
 <tr> 
 <td> global integer M,n; global real W(1:n); global boolean X(1:n) real&nbsp; r,s; integer k,j &nbsp;&nbsp;&nbsp;&nbsp; //生成左儿子// &nbsp;&nbsp; X(k)←1 &nbsp;&nbsp; if s+W(k)=M then &nbsp;&nbsp;&nbsp;&nbsp; print(X(j),j←1 to k) &nbsp;&nbsp; else &nbsp;&nbsp;&nbsp;&nbsp; if s+W(k)+W(k+1)&lt;=M then &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; call SUMOFSUB(S+W(k),k+1,r-W(k)) &nbsp;&nbsp;&nbsp; endif &nbsp;endif &nbsp;&nbsp;&nbsp;&nbsp; //生成右儿子和计算Bk的值// &nbsp;if&nbsp;&nbsp; s+r-W(k)&gt;=M and s+W(k+1)&lt;=M &nbsp;then X(k)←0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; call SUMOFSUB(s,k+1,r-W(k)) &nbsp;endif end SUMOFSUB </td> 
 </tr> 
 </tbody> 
</table>

### 例子 ###

n=6, M=30,W(1:6)=(5,10,12,13,15,18)

![20130516100123669][]

（当前和，当前处理的子数，剩余子数的和）

[20130516100123669]: https://img-blog.csdn.net/20130516100123669