wine.java

八八三分酒问题java实现

/**
 *883分酒问题回溯解法
 * @author 小龙
 */
public class wine {

  int state[][] = new int[10000][8];//状态集，state[i][7]表示步数，state[i][0]～state[i][6]表示cup的状态
  int cup[] = {8, 8, 0, 0, 0, 0, 0};//将酒瓶、酒杯、人均视为cup，只不过容量不同，而且人只能接受不能倒出
  int step[][] = new int[100][3];//保存倒酒过程
  int lastState = 0;
  boolean find = false;

  public static void main(String args[]) {
    wine w = new wine();
    w.solve(0);
  }
//从a编号对象往b编号对象转移时，判断转移的酒量

  int howMuch(int a, int b) {
    int wine;
    if (cup[a] == 0) {
      return 0;
    }
    if (a == b) {
      return 0;
    }
    if (a > 2) {
      return 0;//不能从人往容器转移

    }
    if (b < 3)//容器往容器
    {
      wine = b < 2 ? 8 - cup[b] : 3 - cup[b];
      if (cup[a] < wine) {
        return cup[a];
      }
      return wine;
    } else//容器往人
    {
      wine = 4 - cup[b];
      if (cup[a] > wine) {
        return 0;
      }
      return cup[a];
    }
  }
//解决函数，递归实现

  void solve(int c) {
    //如果已经找到解决方案，则不再探索
    if (find) {
      return;
    //遍历以前记录的所有的状态
    }
    for (int i = 0; i < lastState; i++) {
      int j;
      for (j = 0; j < 7; j++) {
        if (cup[j] != state[i][j]) {
          break;
        //满足j==7,即没有出现break，出现了曾经出现过的状态
        }
      }
      if (j == 7) {
        return;
      }
    }
    //将当前状态设为最后一个状态，用于参与下一次的比较
    for (int j = 0; j < 7; j++) {
      state[lastState][j] = cup[j];
    }
    state[lastState][7] = c;
    lastState++;

    if (cup[0] == 0 && cup[1] == 0 && cup[2] == 0) {
      //初始化状态
      cup[0] = 8;
      cup[1] = 8;
      for (int i = 2; i < 7; i++) {
        cup[i] = 0;
      }
      System.out.println("(" + cup[0] + "," + cup[1] + "," + cup[2] + "," + cup[3] + "," + cup[4] + "," + cup[5] + "," + cup[6] + ")\n");//输出初状态

      for (int i = 0; i < c; i++) {
        cup[step[i][0]] -= step[i][2];
        cup[step[i][1]] += step[i][2];
        System.out.println("(" + cup[0] + "," + cup[1] + "," + cup[2] + "," + cup[3] + "," + cup[4] + "," + cup[5] + "," + cup[6] + ")\n");//依次输出过程状态及结果

      }
      find = true;//标志已经找到解法

    }
    int a, b, n;
    for (a = 0; a < 3; ++a) {
      for (b = 0; b < 7; ++b) {
        if ((n = howMuch(a, b)) > 0) {
          //记录每次倒酒或喝酒的情况，即谁(a)倒酒给谁(b)，或者谁(b)从哪里(a)喝酒，以及酒的量n,以便输出状态列表
          step[c][0] = a;
          step[c][1] = b;
          step[c][2] = n;
          //倒酒或喝酒
          cup[a] -= n;
          cup[b] += n;
          //递归
          solve(c + 1);
          //回溯
          cup[a] += n;
          cup[b] -= n;
        }
      }
    }
  }
}