子集和问题就是 给出一个数组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)按非降次序排列。
global integer M,n; global real W(1:n); global boolean X(1:n) |
例子
n=6, M=30,W(1:6)=(5,10,12,13,15,18)
（当前和，当前处理的子数，剩余子数的和）