回溯法——子集和问题

子集和问题

问题描述：

子集和问题的一个实例为<S,t>。

其中，S={s1,x2,...,xn}是一个正整数的集合，c是一个正整数。

子集和问题判定是否存在S的一个子集S1，使得集合中所有元素的和等于c。

试设计一个解子集和问题的回溯法。

算法设计：

对于给定的正整数集合S={s1,x2,...,xn}和正整数c，计算S的一个子集，使得子集和为c

数据输入：

由文件input.txt提供输入数据。

文件第1行有2个整数n和c，n表示S的大小，c是子集和的目标值。

接下来的1行中，有n个正整数，表示集合S中的元素。

结果输出：

将子集和问题的解输出到文件output.txt。

当问题无解时，输出“No Solution！”。

• 输入文件示例

input.txt
5 10
2 2 6 5 4

• 输出文件示例

output.txt
2 2 6

算法思路：

• 回溯法的步骤为：
  • 修改当前节点状态
  • 递归子节点状态
  • 回改当前节点状态
• backtracking函数：
  • 我们将value的值加上当前节点的值，同时添加当前元素到tem数组里。
  • 递归下一节点，backtracking(i + 1, n, c, S, tem, answer, value);
  • 弹出tem数组刚刚添加的元素，value减去刚才加上的值
  • 如果value值等于c，那么就添加此时的tem数组到answer二维数组中
• ssumc函数：
  • 如果answer二维数组为空，则返回tem数组
  • 如果answer不为空，则返回answer数组的第一个元素
• main函数：
  • 从文件输入n、c、S数组
  • 数组ans等于函数ssumc函数的返回值
  • 输出数组元素，如果为空，则输出“No Solution！”到文件中

代码：

#include <bits/stdc++.h>
using namespace std ;

ifstream infile("input.txt");
ofstream outfile("outfile.txt");

void backtracking(int pos, int &n, int &c, vector<int> S, vector<int> &tem,  vector<vector<int>> &answer, int value);

vector<int> ssumc(int n, int c, vector<int> S) {
	vector<vector<int>> answer;
	vector<int> tem;
	int value = 0;
	int i = 0;
	backtracking(i, n, c, S, tem, answer, value);
	if (!answer.empty())
		return answer[0];
	else
		return tem;
}

void backtracking(int pos, int &n, int &c, vector<int> S, vector<int> &tem, vector<vector<int>> &answer, int value) {
	if (value == c) {
		answer.push_back(tem);
		return ;
	}
	for (int i = pos; i < n; i++) {
		tem.push_back(S[i]);
		value += S[i];

		backtracking(i + 1, n, c, S, tem, answer, value);

		tem.pop_back();
		value -= S[i];
	}
}

int main() {
	vector<int> S;
	int n, c;
	infile >> n >> c;
	for (int i = 0; i < n; i++) {
		int tem;
		infile >> tem;
		S.push_back(tem);
	}

	vector<int> ans = ssumc(n, c, S);

	for (auto it = ans.begin(); it != ans.end(); it++) {
		outfile << *it << " ";
	}
	if (ans.empty())
		outfile << "No Soution!";

	return 0;
}

总结

顾名思义，回溯法的核心是回溯。

在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。

这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。