倒水问题（Fill, UVa 10603）Java算法实现BFS+PriorityQueue优先队列
倒水问题（Fill, UVa 10603）
有装满水的6升的杯子、空的3升杯子和1升杯子，3个杯子中都没有刻度。在不使用其他 道具的情况下，是否可以量出4升的水呢？
倒水问题：一种方法是(6,0,0)→(3,3,0)→(3,2,1)→(4,2,0)
注意：由于没有刻度，用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯 子x倒空，而不能中途停止。
你的任务是解决一般性的问题：设3个杯子的容量分别为a, b, c，最初只有第3个杯子装 满了c升水，其他两个杯子为空。最少需要倒多少升水才能让某一个杯子中的水有d升呢？如 果无法做到恰好d升，就让某一个杯子里的水是d’升，其中d’<d并且尽量接近d。 （1≤a,b,c,d≤200）。要求输出最少的倒水量和目标水量（d或者d’）。
分析
大致思想是通过解答树完成，利用BFS算法，假设在某一时刻，第1个杯子中有v0升水，第2个杯子中有v1升水，第3个杯子中有v2升水，称当时的系统状态为(v0,v1,v2)。这里提到了“状态”这个词，它是理解很多概念和算法的关键。简单地说，它就是“对系统当前状况的描述”。例如，在国际象棋中，当前游戏者 和棋盘上的局面就是刻画游戏进程的状态。
把“状态”想象成树中的结点，可以得到如下解答树。
注意：本题的目标是倒的水量最少，而不是步数最少。实际上，水量最少时步数不一定 最少，例如a=1, b=12, c=15, d=7，倒水量最少的方案是C->A, A->B重复7次，最后C里有7 升水。一共14步，总水量也是14。还有一种方法是C->B，然后B->A, A->C重复4次，最后C 里有7升水。一共只有10步，但总水量多达20。
因此，需要改进一下算法：不是每次取出步数最少的结点进行扩展，而是取出水量最少的结点进行扩展。这样的程序只需要把队列queue换成优先队列PriorityQueue，其他部分的代码不变。
代码
以下代码纯手工编写，欢迎指出错误和优化方法。
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
/**
* 倒水问题（Fill, UVa 10603）
*
* 有装满水的6升的杯子、空的3升杯子和1升杯子，3个杯子中都没有刻度。在不使用其他 道具的情况下，是否可以量出4升的水呢？
*
* 注意： 由于没有刻度，用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯子x倒空，而不能中途停止。
*
* 你的任务是解决一般性的问题： 设3个杯子的容量分别为a, b, c，最初只有第3个杯子装
* 满了c升水，其他两个杯子为空。最少需要倒多少升水才能让某一个杯子中的水有d升呢？如
* 果无法做到恰好d升，就让某一个杯子里的水是d'升，其中d'<d并且尽量接近d。
* （1≤a,b,c,d≤200）。要求输出最少的倒水量和目标水量（d或者d'）。
*
*/
public class Main {
public static int goal;// 需要获取的最终水量
public static int[] glassMax = new int[3];// 各个杯子最大容积
public static Node originNode;// 初始状态杯子内存有的水量
public static int nearestNum = -1;// 最接近目标水量的水量
public static int lowest = Integer.MAX_VALUE; // 最接近目标水量或已达到最优水量的最少倒水量
public static Node lowestNode;// //最接近目标水量或已达到最优水量的最少倒水量情况（结点）
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
glassMax[0] = sc.nextInt();
glassMax[1] = sc.nextInt();
glassMax[2] = sc.nextInt();
goal = sc.nextInt();
initOriginNode();// 初始化originNode节点
BlockOut();// 此方法利用多线程限制时间，用于防止计算超时，给出当前可行解（未必是最优解，碰运气！）
try {
bfs();// 通过广度优先生成树并检索最优解
printResult();// 输出最优解
} catch (Exception e) {
}
System.exit(0);
}
}
/**
* 此方法利用初始化originNode节点
*/
public static void initOriginNode() {
int maxIndex = -1;
int maxValue = -1;
for (int i = 0; i < glassMax.length; i++) {
if (glassMax[i] > maxValue) {
maxValue = glassMax[i];
maxIndex = i;
}
}
int[] picOrigin = new int[glassMax.length];// 各个杯子最大容积
Arrays.fill(picOrigin, 0);
picOrigin[maxIndex] = maxValue;
originNode = new Node(picOrigin);
lowestNode = originNode;
}
/**
* 此方法利用多线程限制时间，用于防止计算超时，给出当前可行解（未必是最优解，碰运气！）
*/
public static void BlockOut() {
Runnable run = new Runnable() {
@Override
public void run() {
try {
Thread.sleep(2900);
printResult();
} catch (Exception e) {
} finally {
System.exit(0);
}
}
};
new Thread(run).start();
}
/**
* 输出最优解
*
* @throws CloneNotSupportedException
*/
public static void printResult() throws CloneNotSupportedException {
Stack<Node> stack = new Stack<Node>();
Node pre = lowestNode;
stack.add(pre.clone());
do {
pre = pre.paNode;
stack.add((Node) pre.clone());
} while (pre.paNode != pre);
for (int i = 0; !stack.isEmpty(); i++) {
System.out.println("Step" + i + ":"
+ Arrays.toString(stack.pop().pic));
}
if (nearestNum != goal) {
System.out.println("无法找到最优解，最接近的可得目标容量：" + nearestNum);
}
System.out.println("其最少倒水量：" + lowest);
}
/**
* 通过广度优先生成树并检索最优解
*/
public static void bfs() {
PriorityQueue<Node> queue = new PriorityQueue<Node>();
queue.add(originNode);
while (!queue.isEmpty()) {
Node keyNode = queue.remove();
// 检索操作，对当前结点和当前解进行判断
if (nearestNum != goal) {
if (keyNode.getNear() > nearestNum) {
nearestNum = keyNode.getNear();
lowestNode = keyNode;
lowest = keyNode.addStepNumTotal;
}
} else {
if (lowestNode.isGoal()) {
if (keyNode.isGoal()) {
if (keyNode.addStepNumTotal <= lowest) {
lowest = keyNode.addStepNumTotal;
lowestNode = keyNode;
}
}
} else {
if (keyNode.isGoal()) {
lowest = keyNode.addStepNumTotal;
lowestNode = keyNode;
} else {
if (keyNode.addStepNumTotal <= lowest
&& keyNode.addStepNumTotal != 0) {
lowest = keyNode.addStepNumTotal;
lowestNode = keyNode;
}
}
}
}
for (int item = 0; item < glassMax.length; item++) {
for (int other = 0; other < glassMax.length; other++) {
// item代表被倒入水的杯子索引，other代表从某个杯子向item杯子倒水
// 粗剪枝
if (item == other) {
continue;
}
if (keyNode.pic[other] == 0) {
continue;
}
if (keyNode.pic[item] == glassMax[item]) {
continue;
}
// 生产新节点
int[] newPic = keyNode.pic.clone();
int beforeNum = newPic[item];
int addNum = newPic[other];
newPic[item] = (beforeNum + addNum <= glassMax[item] ? beforeNum
+ addNum
: glassMax[item]);
newPic[other] = (beforeNum + addNum <= glassMax[item] ? 0
: addNum - glassMax[item] + beforeNum);
Node newNode = new Node(newPic, keyNode.addStepNumTotal
+ newPic[item] - beforeNum, keyNode);
// 判断是否已经出现过这样的情况
boolean sameFlag = false;
Node judge = newNode;
do {
judge = judge.paNode;
if (newNode.equals(judge)) {
sameFlag = true;
break;
}
} while (judge != judge.paNode);
if (sameFlag) {
continue;
}
queue.add(newNode);
}
}
}
}
}
class Node implements Comparable<Node>, Cloneable {
public int pic[];// 以数组形式存放当前情况下各个杯子的水量
public int addStepNumTotal = 0;// 执行到此步时共倒水量
public Node paNode;// 父节点，代表产生这个情况的上一种情况
/**
* 此构造方法仅可用于初始化originNode来构造
*
* @param pic
*/
public Node(int pic[]) {
this.pic = pic;
this.paNode = this;
}
/**
* 此构造方法仅可用于产生新情况（新结点）使用
*
* @param pic
* @param addNumTotal到这步总共增倒水量
* @param pa父节点
* ，代表产生这个情况的上一种情况
*/
public Node(int pic[], int addNumTotal, Node pa) {
this.pic = pic;
this.addStepNumTotal = addNumTotal;
this.paNode = pa;
}
/**
* 用于剪枝操作，对比两个情况是否相同
*/
public boolean equals(Object obj) {
if (obj instanceof Node) {
Node objNode = (Node) obj;
return Arrays.equals(this.pic, objNode.pic);
}
return false;
}
/**
* 此方法判断是否出现解
*
* @return
*/
public boolean isGoal() {
for (int i = 0; i < this.pic.length; i++) {
if (this.pic[i] == Main.goal) {
return true;
}
}
return false;
}
/**
* 此方法返回最接近目标的水量
*
* @return
*/
public int getNear() {
int nearest = -1;
for (int i = 0; i < this.pic.length; i++) {
if (this.pic[i] <= Main.goal && this.pic[i] > nearest) {
nearest = this.pic[i];
}
}
return nearest;
}
/**
* 此方法用于优先队列中，快速对优先的情况进行判断
*/
@Override
public int compareTo(Node obj) {
if (this.isGoal()) {
if (obj.isGoal()) {
if (this.addStepNumTotal <= obj.addStepNumTotal) {
return 1;
} else {
return -1;
}
} else {
return 2;
}
} else {
if (obj.isGoal()) {
return -2;
} else {
return 0;
}
}
}
/**
* 克隆当前情况（浅复制）
*/
public Node clone() throws CloneNotSupportedException {
return (Node) super.clone();
}
}
输出结果
测试数据：96 97 199 62
Step0:[0, 0, 199]
Step1:[96, 0, 103]
Step2:[0, 96, 103]
Step3:[96, 96, 7]
Step4:[95, 97, 7]
Step5:[95, 0, 104]
Step6:[0, 95, 104]
Step7:[96, 95, 8]
Step8:[94, 97, 8]
Step9:[94, 0, 105]
Step10:[0, 94, 105]
Step11:[96, 94, 9]
Step12:[93, 97, 9]
Step13:[93, 0, 106]
Step14:[0, 93, 106]
Step15:[96, 93, 10]
Step16:[92, 97, 10]
Step17:[92, 0, 107]
Step18:[0, 92, 107]
Step19:[96, 92, 11]
Step20:[91, 97, 11]
Step21:[91, 0, 108]
Step22:[0, 91, 108]
Step23:[96, 91, 12]
Step24:[90, 97, 12]
Step25:[90, 0, 109]
Step26:[0, 90, 109]
Step27:[96, 90, 13]
Step28:[89, 97, 13]
Step29:[89, 0, 110]
Step30:[0, 89, 110]
Step31:[96, 89, 14]
Step32:[88, 97, 14]
Step33:[88, 0, 111]
Step34:[0, 88, 111]
Step35:[96, 88, 15]
Step36:[87, 97, 15]
Step37:[87, 0, 112]
Step38:[0, 87, 112]
Step39:[96, 87, 16]
Step40:[86, 97, 16]
Step41:[86, 0, 113]
Step42:[0, 86, 113]
Step43:[96, 86, 17]
Step44:[85, 97, 17]
Step45:[85, 0, 114]
Step46:[0, 85, 114]
Step47:[96, 85, 18]
Step48:[84, 97, 18]
Step49:[84, 0, 115]
Step50:[0, 84, 115]
Step51:[96, 84, 19]
Step52:[83, 97, 19]
Step53:[83, 0, 116]
Step54:[0, 83, 116]
Step55:[96, 83, 20]
Step56:[82, 97, 20]
Step57:[82, 0, 117]
Step58:[0, 82, 117]
Step59:[96, 82, 21]
Step60:[81, 97, 21]
Step61:[81, 0, 118]
Step62:[0, 81, 118]
Step63:[96, 81, 22]
Step64:[80, 97, 22]
Step65:[80, 0, 119]
Step66:[0, 80, 119]
Step67:[96, 80, 23]
Step68:[79, 97, 23]
Step69:[79, 0, 120]
Step70:[0, 79, 120]
Step71:[96, 79, 24]
Step72:[78, 97, 24]
Step73:[78, 0, 121]
Step74:[0, 78, 121]
Step75:[96, 78, 25]
Step76:[77, 97, 25]
Step77:[77, 0, 122]
Step78:[0, 77, 122]
Step79:[96, 77, 26]
Step80:[76, 97, 26]
Step81:[76, 0, 123]
Step82:[0, 76, 123]
Step83:[96, 76, 27]
Step84:[75, 97, 27]
Step85:[75, 0, 124]
Step86:[0, 75, 124]
Step87:[96, 75, 28]
Step88:[74, 97, 28]
Step89:[74, 0, 125]
Step90:[0, 74, 125]
Step91:[96, 74, 29]
Step92:[73, 97, 29]
Step93:[73, 0, 126]
Step94:[0, 73, 126]
Step95:[96, 73, 30]
Step96:[72, 97, 30]
Step97:[72, 0, 127]
Step98:[0, 72, 127]
Step99:[96, 72, 31]
Step100:[71, 97, 31]
Step101:[71, 0, 128]
Step102:[0, 71, 128]
Step103:[96, 71, 32]
Step104:[70, 97, 32]
Step105:[70, 0, 129]
Step106:[0, 70, 129]
Step107:[96, 70, 33]
Step108:[69, 97, 33]
Step109:[69, 0, 130]
Step110:[0, 69, 130]
Step111:[96, 69, 34]
Step112:[68, 97, 34]
Step113:[68, 0, 131]
Step114:[0, 68, 131]
Step115:[96, 68, 35]
Step116:[67, 97, 35]
Step117:[67, 0, 132]
Step118:[0, 67, 132]
Step119:[96, 67, 36]
Step120:[66, 97, 36]
Step121:[66, 0, 133]
Step122:[0, 66, 133]
Step123:[96, 66, 37]
Step124:[65, 97, 37]
Step125:[65, 0, 134]
Step126:[0, 65, 134]
Step127:[96, 65, 38]
Step128:[64, 97, 38]
Step129:[64, 0, 135]
Step130:[0, 64, 135]
Step131:[96, 64, 39]
Step132:[63, 97, 39]
Step133:[63, 0, 136]
Step134:[0, 63, 136]
Step135:[96, 63, 40]
Step136:[62, 97, 40]
其最少倒水量：9859
Studying & Working in Programming and Photography.
E-mail : [email protected]
More About Me : www.magicdevil.top
Love Sharing & Open Source.