subsum.txt

回溯法求子集和问题, 在回溯过程中利用了剪枝

template <class Type>
class Subsum
{
	friend void subsum(Type[], Type, int, int[]);
private:
	bool Backtrack(int i);
	int n,       
		*x,       
		*bestx;   
	Type *w,     
		c,       
		cw,		 
		bestw,	
		r;		  
};

template <class Type>
bool Subsum<Type>::Backtrack(int i)
{//搜索第i层节点
	if (i > n)  //到达叶节点
	{
		for (int j = 1; 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;
}

template <class Type>
void subsum(Type w[], Type c, int n, int bestx[])
{
	Subsum<Type> X;
	//初始化X
	X.x = new int[n + 1];
	X.w = w;
	X.c = c;
	X.n = n;
	X.bestx = bestx;
	X.bestw = 0;
	X.cw = 0;
	//初始化r
	X.r = 0;
	for (int i = 1; i <= n; i++)
		X.r += w[i];
	if (X.Backtrack(1))
	{
		for (i = 1; i <= n; i++)
		{
			if (bestx[i] == 1)
				cout << w[i] << " ";
		}
		cout << endl;
	}
	else
		cout << "No Solution!" << endl;
	delete []X.x;
}

#include <iostream>
using namespace std;

int main()
{
	int n, c, i;
	cin >> n >> c;
	int *bestx = new int[n + 1];
	int *w = new int[n + 1];
	for (i = 1; i <= n; i++)
		cin >> w[i];
	subsum(w, c, n, bestx);
	return 0;
}