回溯法:Xenia and Weights

问题描述
给定 n 种砝码,重量位于区间 [1,10] ，不同种类砖码重量互不相同,且每种砝码的数量不限。轮流在天平两侧放砖码，要求：每次所使用的砝码与前一次不同(第一次可以为任意重量)，且当前放置砝码的一侧放置砝码后比另一侧重 。问能否进行 m 次操作，如果能，输出任意一种方案，如果不能，输出NO。

分析
思路大致和之前回溯法章节相同，只是需要左右两边分开处理。process() 的参数较多，这是因为笔者个人偏好 利用函数栈自动完成回溯法所需要的撤销操作，所以必须用参数（而且必须为值传递）；也可以用全局变量，然后再递归后手动撤销。 详细过程不再阐述，代码注释已经解释清楚：

#include<iostream>
#include<cstdlib>//rand()
#include<ctime>//time()
#include<cstring>//memcpy()
#include<vector>

enum turn{LEFT,RIGHT};
int weights[2][10] = { {1,2,3,4,5,6,7,8,9,10} //砝码种类
					  ,{0,0,0,0,0,0,0,0,0,0}};//1代表有此种类
int count = 0;//设定的操作次数
std::vector<int> temp;

/*    lw:左盘总重 rw:右盘总重 m:当前操作的次数 temp:记录每次放下的砝码重量  t:轮到哪边放*/
void process(int lw,int rw,int w, int m,std::vector<int> temp,turn t)
{
	if (count == -1)
		return;
	if (m == count)
	{
		count = -1;//将count设置为1，后续不再dfs，直接返回
		for (int i : temp)
			std::cout << i << " ";
	}	
	if (t == turn::LEFT)//本次在左盘放置砝码
	{
		if (lw + w <= rw)
			return;
		else
		{
			lw += w;
			m++;
			temp.push_back(w);
			for (int i = 0; i < 10; i++)
			{
				if (weights[1][i] == 0 || w == i+1)//w==i+1代表如果本次放下的重量等于上次的重量,则跳过
					continue;
				process(lw, rw, weights[0][i], m, temp, turn::RIGHT);
			}
		}
	}

	if (t == turn::RIGHT)
	{
		if (rw + w <= lw)
			return;
		else
		{
			rw += w;
			m++;
			temp.push_back(w);
			for (int i = 0; i < 10; i++)
			{
				if (weights[1][i] == 0 || w == i+1)
					continue;
				process(lw, rw, weights[0][i], m, temp, turn::LEFT);
			}
		}
	}
}

void put(int count)//启动子
{
	for (int i = 0; i < 10; i++)
	{
		if (weights[1][i] == 0)
			continue;
		process(0, 0, weights[0][i], 0, temp, turn::LEFT);
	}
}
int main()
{
	weights[1][7] = 1;
	weights[1][9] = 1;
	weights[1][1] = 1;
	count = 7;
	put(count);
}