子集和问题子集和问题的一个为〈St〉。其中，S={x1x2...xn}是一个正整数的集合，c

子集和问题 Description 子集和问题的一个实例为〈S,t〉。其中，S={x1,x2,...,xn}是一个正整数的集合，c 是一个正整数。子集和问题判定是否存在S的一个子集S1，使得x∈S1,∑x=c. 试设计一个解子集和问题的回溯法。 «编程任务： 对于给定的正整数的集合S={x1,x2,...,xn}和正整数c，编程计算S 的一个子集 S1，使得x∈S1,∑x=c. Input 由文件input.txt 提供输入数据。文件第1 行有2 个正整数n 和c，n 表示S 的大小，c 是子集和的目标值。接下来的1 行中，有n 个正整数，表示集合S 中的元素。 Output 程序运行结束时，将子集和问题的解输出到文件output.txt中。 当问题无解时，输出“No Solution!”。 Sample Input 5 10 2 2 6 5 4 Sample Output 2 2 6

#include 
#include 
using namespace std;
ifstream cin（“1.in“）;
ofstream cout（“1.out“）;
int nccwrbestw;
vector  x;
vector  w;
vector  bestx;

bool backtrack（int i）
{
	if （i > n - 1）
	{
		if （cw > bestw）
		{
			for（int j = 0; j < n; j++）
				bestx[j] = x[j];
			bestw = cw;

			if （bestw == c） return true;
			else
				return false;
		}
	}

	r -= w[i];
	if （cw + w[i] <= c）
	{
		x[i] = 1;
		cw += w[i];
		if （backtrack（i+1））
			return true;
		cw -= w[i];
	}

	if （cw + r > bestw）
	{
		x[i] = 0;
		if （backtrack（i+1））
			return true;
	}

	r += w[i];
	return false;
}

int main（）
{
	int i;
	cin >> n >> c;
	x.resize（n）;
	w.resize（n）;
	bestx.resize（n）;
	cw = 0;
	bestw = 0;
	r = 0;
	for（i = 0; i < x.size（）; i++）
	{
		cin >> w[i];
		r += w[i];
		x[i] = 0;
		bestx[i] = 0;
	}

	if （backtrack（0））
	{
		for（i = 0; i < n; i++）
			if （bestx[i] == 1）	
				cout << w[i] << “ “;
	}
	else
		cout << “No Solution!“;
	cout << endl;
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1039  2008-11-22 12:46  子集和问题\1076.cpp

     文件      24576  2009-03-13 19:17  子集和问题\子集和问题.doc

     目录          0  2009-03-13 19:17  子集和问题

----------- ---------  ---------- -----  ----

                25615                    3