题目:
标题:分红酒
有4个红酒瓶子,它们的容量分别是:9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0],也就是说:第一个瓶子满着,其它的都空着。
允许把酒从一个瓶子倒入另一个瓶子,但只能把一个瓶子倒满或把一个瓶子倒空,不能有中间状态。这样的一次倒酒动作称为1次操作。
假设瓶子的容量和初始状态不变,对于给定的目标状态,至少需要多少次操作才能实现?
本题就是要求你编程实现最小操作次数的计算。
输入:最终状态(逗号分隔)
输出:最小操作次数(如无法实现,则输出-1)
例如:
输入:
9,0,0,0
应该输出:
0
输入:
6,0,0,3
应该输出:
-1
输入:
7,2,0,0
应该输出:
2
分析:
对于状态的理解,对于学习算法是非常重要的,尤其是对于搜索的算法和动态规划的算法。我们可以把四个瓶子里面的水的体积抽象成一种状态(a, b, c, d),然后状态转移无非就是a->b, b->a, c-> a, a->c, b->c, c->b, d->a, a->d, d->c, c->d, b->d, d->b共A(4,2) = 3 * 4 = 12种。当然其中有一些操作是无效的,比如a为空,a就不可以倒给其他瓶子了。a要是满,其他瓶子也不能倒给a。
状态定义好了,状态转移的操作也理清了,下一步就是爆搜了。由于这里要的是最少的操作,那就用广度优先搜索。
为了提高搜索的效率,防止一个状态被搜索到多次,我们用一个hash (哈希)标志 状态是否被搜到过。
为了代码编起来简洁一些,我们定义一个数组bot[4]存储每个瓶子里面的酒的体积。 具体见代码。
算法框架:
1、用一个数组end[4]记录目标状态,并输入状态
2、用一个数组cap[4]记录每个瓶子的最大容量
3、将初始状态放入队列
4、从队列中取出队头的状态
5、判断是否是目标状态,是的话直接输入到达该状态需要多少步,算法结束
6、执行12中可能的操作,当然其中有一些不可行,得到操作后的状态,放入队列
7、重复4、5、6直到队列为空,则输出-1,否则必从5输出了结果
代码:
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> using namespace std; struct State { int bot[4], step; }; int cap[5] = {9, 7, 4, 2}; bool vis[10][8][5][3]; bool pour(State& tmp, int i, int j) { if(tmp.bot[i] == 0) return false; if(tmp.bot[j] == cap[j]) return false; if(tmp.bot[i] + tmp.bot[j] <= cap[j]) { tmp.bot[j] = tmp.bot[i] + tmp.bot[j]; tmp.bot[i] = 0; } else { tmp.bot[i] -= (cap[j] - tmp.bot[j]); tmp.bot[j] = cap[j]; } if(vis[tmp.bot[0]][tmp.bot[1]][tmp.bot[2]][tmp.bot[3]]) { return false; } else { vis[tmp.bot[0]][tmp.bot[1]][tmp.bot[2]][tmp.bot[3]] = 1; } tmp.step ++; return true; } int main(void) { memset(vis, 0, sizeof(vis)); int end[5]; for(int i = 0; i < 4; i ++) scanf("%d", &end[i]); queue<State> q; q.push((State){{9, 0, 0, 0},0}); bool flag = false; while(!q.empty()) { State tmp = q.front(); q.pop(); int i; for(i = 0; i < 4; i ++) { if(tmp.bot[i] != end[i]) break; } if(i == 4) { flag = true; printf("%d\n", tmp.step); break; } for(int i = 0; i < 4; i ++) { for(int j = 0; j < 4; j ++)if(i != j) { State tmp2 = tmp; if(pour(tmp2, i, j)) { q.push(tmp2); } } } } if(!flag) printf("-1\n"); return 0; }