回溯法: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);
}
版权声明:
本站所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
后端技术分享!
喜欢就支持一下吧