子集和数问题（回溯法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了子集和数问题（回溯法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【问题描述】给定一个n个整数的集合X={x1,x2,…xn}(X中可能包含重复元素)和整数y，找出和等于y的X的子集Y。例如说，如果X={10,30,20,60,40,50}，和y=60,则有4种不同的解，他们分别是{10,20,30},{10,50},{20,40},{60}。
【输入形式】输入的第1行包含两个整数n和y，分别表示集合X的长度和目标整数y。接下来1行包含n个整数(整数之间以空格分割)，表示X中的n个元素。
【输出形式】输出1或0，若存在解，输出1，不存在则输出0。
【样例输入】

6 60

10 30 20 60 40 50
【样例输出】

题解：

解向量：
此题的解向量，严格来说，有两种。以题干中的例子 $W$ ={10,30,20,60,40,50}来说明，一种是题干中所给出的变长解{10,20,30}，{10,50}，{20,40}，{60}；另一种就是使用布尔向量表示的定长解 $x_1$ ={1,1,1,0,0,0}， $x_2$ ={1,0,0,0,0,1}， $x_3$ ={0,0,1,0,1,0}， $x_4$ ={0,0,0,1,0,0}，0和1也就表示的是此位置的数选或者不选。本题解采用的是定长解向量。

规范函数：
设 $w [i]$ 为第 $W$ 中的第 $i$ 个数，则有 $\sum w[i]*x[i]=y$ ，说人话的话，由于 $x [i]$ 的取值只有0或者1，因此若 $x [i]$ 为0，也就是第 $i$ 个数没有被选中时， $w [i] * x [i]$ 就为0，所以前面的式子的意思就是所有的解必须满足选中的 $w [i]$ 求和等于 $y$

其实我们明确了解向量和规范函数之后就可以暴力地写一个深搜了，把所有可能地解都枚举一遍，只要找到满足规范函数的一个解向量就 $r e t u r n$ 。

bool flag=false;
void dfs(int k, int sum){
	if(k>n){
		return;
	}
	if(sum==y){
		flag=true;
		return;
	}
	//选第k个数的情况
	x[k]=1;
	dfs(k+1,sum+w[k]);
	//不选第k个数的情况
	x[k]=0;
	dfs(k+1,sum);
}

虽然这样写，思路很简单，但是时间复杂度高达 $2^n$ （每个数有2种选择，选或者不选，组合起来总的选择数就为 $2^n$ ），而且做了很多没有必要的搜索，因此，有必要进行剪枝。文章来源地址https://www.toymoban.com/news/detail-492400.html

由于此题中的 $w$ 集合中元素的顺序对我们解决问题不会产生影响，我们首先对输入的 $w$ 数组进行从小到大的排序。
我们为dfs函数的参数添加两个形参， $s$ 表示前 $k - 1$ 个数的范围内选中的数的和， $r$ 表示还未搜索的数之和，显然， $r + s = s u m$ 总是成立的
当我们考虑选中第 $k$ 个数的时候，我们预想一下，如果加上第 $k + 1$ 个数的话， $s$ 的值超过了 $y$ ，那么其实我们就没有必要选第 $k$ 个数了，因为继续搜索下去不可能搜索到解。而且我们事先已经排好了序，如果加上 $w [k + 1]$ 大于 $y$ ，那加上 $w [k + 2]$ 肯定也是大于 $y$ 的，因此只需判断是否满足 $s + w [k] + w [k + 1] < = y$ 。
当我们考虑不选第 $k$ 个数的时候，我们需要考虑剩余的数之和 $r$ 和目前的 $s$ 加起来能不能达到 $y$ ，如果不能，说明剩下的数根本不够用，也不可能产生解。除此之外，假如剩下的数足够选，这个时候同样需要判断加上 $w [k + 1]$ 会不会大于 $y$ ，一旦大于了，就没有搜索下去的必要了。

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;
int n, y, w[1001], sum = 0, x[1001];
set<string> vis;
//子集和数问题

bool flag = false;
void dfs(int k, int s, int r) {
    if (k > n) {
        return;
    }
    x[k] = 1;
    if (s + w[k] == y) {
        flag = true;
        return;
    }
    else {
        if (s + w[k] + w[k + 1] <= y) {
            dfs(k + 1, s + w[k], r - w[k]);
            x[k] = 0;
        }
        if (s - w[k] + r >= y && s + w[k + 1] <= y) {
            x[k] = 0;
            dfs(k + 1, s, r);
        }
    }
}

int main()
{
    cin >> n >> y;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    if (sum >= y) {
        sort(w + 1, w + 1 + n);
        dfs(1, 0, sum);
        if (flag)
            cout << 1;
        else {
            cout << 0;
        }
    }
    else {
        cout << 0;
    }
    return 0;
}