<span role="heading" aria-level="2">分酒问题（DFS解法）

大家好，又见面了，我是你们的朋友全栈君。

题目大概是这样：

已知有三个容量分别为3千克、5千克和8千克的并且是没有刻度的酒瓶，3千克和5千克的瓶子均装满了酒，而8千克的瓶子为空。现要求仅用这三个酒瓶将这些酒均分为两个4千克并分别装入5千克和8千克的瓶子中。

题解：

可以扩展为有n个瓶子，每个瓶子当前装了x1,x2,x3…xn的酒，每个瓶子的上限是y1,y2,…yn，目标状态是每个瓶子d1,d2,…dn，现在要从当前状态转换到目标状态

可以解读到，每个瓶子只有两种状态–要么盛满，要么空

所以当酒从x瓶子转移到y瓶的时候，只有可能是试图将酒全部到入y瓶中，这样会造成两种结果：

　　能盛得下– x瓶空，y瓶的酒为原来的酒加上x瓶原来的酒。

　　盛不下– x瓶的酒为原来的酒减去倒过去的那部分， y瓶满。

很显然，如果要求最短的步数，BFS是一个比较简单的办法，现在想输出所有的路径，所以考虑DFS

代码：

import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; //已知有3个容量分别为3kg，5kg和8kg且没有刻度的酒瓶3kg和5kg的瓶子均装满了酒。而8kg的瓶子为空。 //现要求仅用这3个酒瓶将这些酒均分为两个4kg，并分别装入5kg和8kg的瓶子中。 public class DispensingProblem { public static int N; //酒瓶的数量 public static Integer[] bottleMax; //每个酒瓶最多装多少酒 public static Integer[] bottleCurrent; //每个酒瓶现在装了多少酒 public static Integer[] bottleFinal; //标注每个酒瓶的最终状态 public static ArrayList<String> states; //标注每一种状态，防止重复(每一种状态是一个向量，我用整型数组表示) public static ArrayList<String[]> paths; //标注每一条路径 public static int caseNum = 0; //标注是第几种方法 public static int minNum = 1000000; //标注最少需要的步数 public static void dfs(int n){ String testS = String.valueOf(bottleCurrent[0]); for(int m =1;m<N;m++) testS+=String.valueOf(bottleCurrent[m]); boolean flag = true; for(int k = 0;k<N;k++) if(bottleCurrent[k]!=bottleFinal[k]) flag = false; if(flag){ caseNum ++ ; if(n <= minNum){ if(n<minNum){ paths.clear(); } String[] tempS= new String[states.size()]; for(int ll = 0;ll<states.size();ll++) tempS[ll] = states.get(ll); paths.add(tempS); minNum = n; } System.out.println("第"+caseNum+"种方法："); for(int l=0;l<states.size();l++) System.out.println(states.get(l)); System.out.println("总共需要移动"+n+"步"); System.out.println("------------------------------------"); return; } //找出当前可能的所有移动 //数据不大，不需要优化 //每个瓶子只能倒满或者倒空 //注意要标注每一种状态，防止状态重复 for(int i = 0 ; i < N;i++) for(int j = 0; j < N ;j++){ if(i==j) continue; //从i瓶把所有酒倒入j瓶 int nI = bottleCurrent[i]; int nJ = bottleCurrent[j]; int temp = nI + nJ - bottleMax[j]; if(temp<=0){ //能全倒进去 bottleCurrent[i] = 0; bottleCurrent[j] = nI + nJ; String s = String.valueOf(bottleCurrent[0]); for(int m =1;m<N;m++) s+=String.valueOf(bottleCurrent[m]); if(!states.contains(s)){ states.add(s); dfs(n+1); //回溯  states.remove(states.indexOf(s)); } //回溯 bottleCurrent[i] = nI; bottleCurrent[j] = nJ; } else{ //不能全倒进去 bottleCurrent[i] = temp; bottleCurrent[j] = bottleMax[j]; String s = String.valueOf(bottleCurrent[0]); for(int m =1;m<N;m++) s+=String.valueOf(bottleCurrent[m]); if(!states.contains(s)){ states.add(s); dfs(n+1); //回溯  states.remove(states.indexOf(s)); } //回溯 bottleCurrent[i] = nI; bottleCurrent[j] = nJ; } } //找遍所有状态都不可行，则表明不能出现这种状态 //System.out.println("不可能存在这种状态！");  } public static void main(String[] args){ Scanner sc = new Scanner(System.in); System.out.println("请输入瓶子个数"); N = sc.nextInt(); bottleMax = new Integer[N]; bottleCurrent = new Integer[N]; bottleFinal = new Integer[N]; states = new ArrayList<String>(); paths = new ArrayList<String[]>(); System.out.println("请输入每个瓶子的容量"); for(int i = 0 ;i < N; i ++){ bottleMax[i] = sc.nextInt(); } System.out.println("请输入每个瓶子当前有多少酒"); for(int i = 0 ;i < N; i ++){ bottleCurrent[i] = sc.nextInt(); } System.out.println("请输入最终希望每个瓶子有多少酒"); for(int i = 0 ;i < N; i ++){ bottleFinal[i] = sc.nextInt(); } String s = String.valueOf(bottleCurrent[0]); for(int i =1;i<N;i++) s+=String.valueOf(bottleCurrent[i]); states.add(s); dfs(0); System.out.println("******************************"); System.out.println("最少需要"+minNum+"步"); int index = 0; for(int i = 0;i<paths.size();i++){ index++; System.out.println("第"+index+"种最短方法："); String[] temp = paths.get(i); for(int j = 0;j<temp.length;j++) System.out.println(temp[j]); System.out.println("-----------------------------------"); } System.out.println("******************************"); } }