【精选】算法设计与分析（第五章回溯法）

void dfs(int i, int tw, int tv, int rw, int op[])//求解0/1背包问题
{
	if (i > n)				//找到一个叶子结点
	{
		if (tw == W && tv > maxv)	//找到一个满足条件的更优解，保存它
		{
			maxv = tv;
			for (int j = 1; j <= n; j++)	//复制最优解
				x[j] = op[j];
		}
	}
	else                    //尚未找完所有物品
	{
		if (tw + w[i] < W)		//左孩子结点剪枝
		{
			op[i] = 1;			//选取第i个物品
			dfs(i + 1, tw + w[i], tv + v[i], rw - w[i], op);
		}
		if (tw + rw - w[i] >= W)		//右孩子结点剪枝
		{
			op[i] = 0;					//不选取第i个物品，回溯
			dfs(i + 1, tw, tv, rw - w[i], op);
		}
	}
}

void dfs(int i, int tw, int tv, int op[])//求解0/1背包问题
{
	if (i > n)				//找到一个叶子结点
	{
		maxv = tv;			//存放更优解
		for (int j = 1; j <= n; j++)
			x[i] = op[j];
	}
	else                    //尚未找完所有物品
	{
		if (tw + A[i].w <= W)	//左孩子结点剪枝
		{
			op[i] = 1;			//选取序号为i的物品
			dfs(i + 1, tw + A[i].w, tv + A[i].v, op);
		}
		if (bound(i, tw, tv) > maxv)	//右孩子结点剪枝
		{
			op[i] = 0;			//不选取序号为i的物品，回溯
			dfs(i + 1, tw, tv, op);
		}
	}
}

#include<stdio.h>
#define MAXN 20		//最多整数个数
//问题表示
int n = 4, W = 31;
int w[] = { 0,11,13,24,7 };//存放所有整数，不用下标0的元素
int count = 0;		//累计解个数
void dispasolution(int n)//输出一个解
{
	for (int j = 1; j <= n; j++)
		if (w[j] == 1)
			printf("\t将第%d个集装箱装上第一艘轮船\n", j);
		else
			printf("\t将第%d个集装箱装上第二艘轮船\n", j);
}
void dfs(int i, int tw, int rw, int x[])//求解子集和
{	//tw为考虑第i个整数时选取的整数和，rw为剩下的整数和
	if (i > n)//找到一个叶子结点
	{
		if (tw == W)//找到一个满足条件的解，输出它
			dispasolution(tw);
	}
	else            //尚未找完所有整数
	{
		if (tw + w[i] <= W)//左孩子结点剪枝：选取满足条件的整数w[i]
		{
			x[i] = 1;//选取第i个整数
			dfs(i + 1, tw + w[i], rw - w[i], x);
		}
		if (tw + rw - w[i] >= W)//右孩子结点剪枝
		{
			x[i] = 0;			//不选取第i个整数，回溯
			dfs(i + 1, tw, rw - w[i], x);
		}
	}
}
int main() {
	int x[MAXN];
	int rw = 0;//存放一个解向量
	for (int j = 1; j <= n; j++)
		rw += w[j];//求所有整数和rw
	dfs(1, 0, rw, x);//i从1开始
	return 0;
}

#include<stdio.h>
#define MAXN 20		//最多整数个数
//问题表示
int n = 4, W;
int w[] = { 0,11,13,24,7 };	//存放所有整数，不用下标0的元素
bool dfs(int i, int tw, int rw)	//存放所有整数，不用下标0的元素
{
	if (i > n)						//找到一个叶子结点
	{
		if (tw == W)					//找到一个满足条件的解，返回true
		{
			return true;
		}
	}
	else                            //尚未找完所有物品
	{
		if (tw + w[i] <= W)				//左孩子结点剪枝
			return dfs(i + 1, tw + w[i], rw - w[i]);//选取第i个整数
		if (tw + rw - w[i] >= W)				//有孩子结点剪枝
			return dfs(i + 1, tw, rw - w[i]);	//不选取第i个整数，回溯
	}
	return false;
}

int count;						//全局变量，累计解个数
void dfs(int i, int tw, int rw)	//求解子集和
{
	if (i > n)						//找到一个叶子结点
	{
		if (tw == W)					//找到一个满足条件的解，count++
		{
			count++;
		}
	}
	else                            //尚未找完所有物品
	{
		if (tw + w[i] <= W)				//左孩子结点剪枝
			dfs(i + 1, tw + w[i], rw - w[i]);//选取第i个整数
		if (tw + rw - w[i] >= W)				//有孩子结点剪枝
			dfs(i + 1, tw, rw - w[i]);	//不选取第i个整数，回溯
	}
}