一、问题描述

现有8升、5升、3升的容器各一个，均无任何度量标记，其中8升的容器装满啤酒，其他两个为空。要求用上述容器倒来倒去，分成两份4升的啤酒。

二、解决方法

1.定义状态空间

用（x，y，z）三个有序整数表示状态空间的一个状态，
x表示8L瓶中的酒量，x∈[0,8]；
y表示5L瓶中的酒量，y∈[0,5]；
z表示3L瓶中的酒量，z∈[0,3];
起始状态为：（8，0，0），目标状态为（4，4，0）

2.确定一组操作

①x倒入y
②x倒入z
③y倒入x
④y倒入z
⑤z倒入x
⑥z倒入y

3.搜索过程

和水壶问题一样，先初始化状态空间，设置第一个节点的状态为已访问，将此节点加入栈中
随后开始深度优先搜索，以当前节点为父节点，遍历其所有的子节点，若该节点没有被访问过则把该节点的状态加入栈中，并且设为已访问，直到寻找到满足最终状态的节点，输出路径
之后重复这个步骤，直到遍历完所有的路径，递归结束

三、代码实现

1.关键代码

实现深度优先搜索

    private void solve(int a, int b, int c) {
        //判断是否为目标状态
        if (a == 4 && b == 4) {
            print(pos);
            pos++;
        } else {
            for (int i = 1; i <= 6; i++) {
                //依次进行六种操作，并返回操作后的状态
                WaterState news = operate(a, b, c, i);
                //判断是否访问过
                if (checkRepeat(news.a, news.b) == 0) {
                    pathStack.push(news);//入栈
                    space[news.a][news.b] = 1;//设置为已访问
                    solve(news.a, news.b, news.c);//递归
                    pathStack.pop();//出战
                    space[news.a][news.b] = 0;//状态重置
                }
            }
        }
    }

2.全部代码

import java.util.Stack;

public class Beer {
    private int pos = 1;
    //因为三个杯子的总量是确定的，所以可以用一个二维数组来记录
    private int[][] space = new int[9][6];//通过0，1判断状态访问情况
    private Stack<WaterState> pathStack = new Stack();

    public static void main(String[] args) {
        Beer beer = new Beer();
    }

    public Beer() {
        initSpace();//状态空间初始化
        int a = 8;//8L的容器
        int b = 0;//5L的容器
        int c = 0;//3L的容器
        pathStack.push(new WaterState(8, 0, 0));//入栈
        solve(a, b, c);//递归
    }

    //输出
    private void print(int pos) {
        System.out.println("结果" + pos + ":");
        int i = 0;
        int l = pathStack.size();//栈的长度
        while (l > 0) {
            System.out.println(pathStack.get(i).a + "     " + pathStack.get(i).b + "     " + pathStack.get(i).c);
            i++;
            l--;
        }
        System.out.println("操作次数:" + i);
        System.out.println();
    }

    //深度优先搜索
    private void solve(int a, int b, int c) {
        //判断是否为目标状态
        if (a == 4 && b == 4) {
            print(pos);
            pos++;
        } else {
            for (int i = 1; i <= 6; i++) {
                //依次进行六种操作，并返回操作后的状态
                WaterState news = operate(a, b, c, i);
                //判断是否访问过
                if (checkRepeat(news.a, news.b) == 0) {
                    pathStack.push(news);//入栈
                    space[news.a][news.b] = 1;//设置为已访问
                    solve(news.a, news.b, news.c);//递归
                    pathStack.pop();//出战
                    space[news.a][news.b] = 0;//状态重置
                }
            }
        }
    }
    //实现六种操作
    private WaterState operate(int a, int b, int c, int i) {
        switch (i) {
            case 1://a->b
                if (a + b >= 5) {
                    a = a + b - 5;
                    b = 5;
                } else {
                    b = a + b;
                    a = 0;
                }
                break;
            case 2://b->c
                if (b + c >= 3) {
                    b = b + c - 3;
                    c = 3;
                } else {
                    c = b + c;
                    b = 0;
                }
                break;
            case 3://c->a
                a = a + c;
                c = 0;
                break;
            case 4://a->c
                if (a + c >= 3) {
                    a = a + c - 3;
                    c = 3;
                } else {
                    c = a + c;
                    a = 0;
                }
                break;
            case 5://b->a
                a = a + b;
                b = 0;
                break;
            case 6://c->b
                if (b + c >= 5) {
                    c = b + c - 5;
                    b = 5;
                } else {
                    b = b + c;
                    c = 0;
                }
                break;
        }
        return new WaterState(a, b, c);
    }
    //查重
    private int checkRepeat(int a, int b) {
        if (space[a][b] == 1) {
            return 1;
        }
        return 0;
    }
    //状态空间初始化
    private void initSpace() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 6; j++) {
                space[i][j] = 0;
            }
        }
        space[8][0] = 1;
    }
    //内部类，记录状态
    static class WaterState {
        int a, b, c;

        WaterState(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}