问题导入：
倒水问题描述：现在有3L，4L的杯子，无限多的水，要求用这两个容器倒出5L的水，如何求解?
求解具体代码：
/**
* Question:倒水问题描述：现在有3L，4L的杯子，无限多的水，要求用这两个容器倒出5L的水，如何求解?
* Author: ChenPeng
* CompleteTime:2019-04-21
*/
import java.util.*;
/**
* 状态的数据结构(a,b)
* parentNode 用于最终路径回溯
*/
class WaterStatus implements Cloneable {
private int a; // a容器
private int b; // b容器
private WaterStatus parentNode; // 父节点
public WaterStatus(int a, int b) {
this.a = a;
this.b = b;
this.parentNode = null;
}
public void setA(int a) {
this.a = a;
}
public int getA() {
return this.a;
}
public void setB(int b) {
this.b = b;
}
public int getB() {
return this.b;
}
public WaterStatus getParentNode() {
return parentNode;
}
public void setParentNode(WaterStatus parentNode) {
this.parentNode = parentNode;
}
/**
* 判断是否结束
*
* @return
*/
public boolean isEnd() {
return this.a + this.b == 5;
}
/**
* 重写equals方法
*
* @param obj
* @return
*/
@Override
public boolean equals(Object obj) {
if (!(obj instanceof WaterStatus)) {
return false;
}
if (this == obj) {
return true;
}
boolean flag = (((WaterStatus) obj).getA() == this.getA())
&& (((WaterStatus) obj).getB() == this.getB());
return flag;
}
/**
* 重写hashcode方法
*
* @return
*/
@Override
public int hashCode() {
int result = Integer.hashCode(a);
result = 31 * result + Integer.hashCode(b);
return result;
}
/**
* 克隆方法（浅拷贝）
*
* @return
*/
@Override
protected Object clone() {
WaterStatus waterStatus = null;
try {
waterStatus = (WaterStatus) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return waterStatus;
}
/**
* 重写toString方法
*
* @return
*/
@Override
public String toString() {
return "(" + this.a + "," + this.b + ")";
}
}
/**
* 倒水问题求解
*/
public class DaoShui {
// A容器的容量
private static final int A_CONTAINER = 3;
// B容器的容量
private static final int B_CONTAINER = 4;
// 历史状态存储
private static Set<WaterStatus> histroyStatus = new HashSet();
public static void main(String[] args) {
// 初始状态
WaterStatus water = new WaterStatus(0, 0);
histroyStatus.add(water);
// 调用求解5L的路径
calculatePath(water);
}
/**
* 计算路径（核心方法）
*
* @param water
*/
public static void calculatePath(WaterStatus water) {
if (water.isEnd()) { // 算法终止条件是满足最终需要倒出5L水
// 最终路径序列(栈)先进后出
Stack<WaterStatus> resultPath = new Stack<>();
while (water != null) {
resultPath.push(water); // 压入栈中
water = water.getParentNode();
}
// 输出结果
printStack(resultPath);
return;
}
// 存储每一层的中间结果
List<WaterStatus> tempList = new ArrayList<>();
// a <-
WaterStatus waterStatus1 = (WaterStatus) water.clone();
// 这里判断是否能采用该方法&&该方法后不能与之前的状态重合(下同)
if (aGetWater(waterStatus1) && (!histroyStatus.contains(waterStatus1))) {
histroyStatus.add(waterStatus1); // 添加历史记录(下同)
waterStatus1.setParentNode(water); // 设置父节点
tempList.add(waterStatus1); // 保存中间层结果(下同)
} else {
waterStatus1 = null;
}
// b <-
WaterStatus waterStatus2 = (WaterStatus) water.clone();
if (bGetWater(waterStatus2) && (!histroyStatus.contains(waterStatus2))) {
histroyStatus.add(waterStatus2);
waterStatus2.setParentNode(water);
tempList.add(waterStatus2);
} else {
waterStatus2 = null;
}
// a -> b
WaterStatus waterStatus3 = (WaterStatus) water.clone();
if (aTobWater(waterStatus3) && (!histroyStatus.contains(waterStatus3))) {
histroyStatus.add(waterStatus3);
waterStatus3.setParentNode(water);
tempList.add(waterStatus3);
} else {
waterStatus3 = null;
}
// b -> a
WaterStatus waterStatus4 = (WaterStatus) water.clone();
if (bToaWater(waterStatus4) && (!histroyStatus.contains(waterStatus4))) {
histroyStatus.add(waterStatus4);
waterStatus4.setParentNode(water);
tempList.add(waterStatus4);
} else {
waterStatus4 = null;
}
// a ->
WaterStatus waterStatus5 = (WaterStatus) water.clone();
if (aEmpty(waterStatus5) && (!histroyStatus.contains(waterStatus5))) {
histroyStatus.add(waterStatus5);
waterStatus5.setParentNode(water);
tempList.add(waterStatus5);
} else {
waterStatus5 = null;
}
// b ->
WaterStatus waterStatus6 = (WaterStatus) water.clone();
if (bEmpty(waterStatus6) && (!histroyStatus.contains(waterStatus6))) {
histroyStatus.add(waterStatus6);
waterStatus6.setParentNode(water);
tempList.add(waterStatus6);
} else {
waterStatus6 = null;
}
// 强制通知开始垃圾回收,但是不会立即执行
System.gc();
if (tempList.size() > 0) {
// 然后依次递归调用
for (WaterStatus e : tempList) {
calculatePath(e);
}
}
}
/**
* a取水 a <-
*
* @param water
* @return
*/
public static boolean aGetWater(WaterStatus water) {
if (water.getA() == A_CONTAINER) {
return false;
}
water.setA(A_CONTAINER);
return true;
}
/**
* b取水 b <-
*
* @param water
* @return
*/
public static boolean bGetWater(WaterStatus water) {
if (water.getB() == B_CONTAINER) {
return false;
}
water.setB(B_CONTAINER);
return true;
}
/**
* a把水倒入b中 a -> b
*
* @param water
* @return
*/
public static boolean aTobWater(WaterStatus water) {
int a = water.getA();
int b = water.getB();
if (a == 0 || b == B_CONTAINER) {
return false;
}
if (a + b > B_CONTAINER) {
water.setB(B_CONTAINER);
water.setA(a + b - B_CONTAINER);
} else {
water.setA(0);
water.setB(a + b);
}
return true;
}
/**
* b把水倒入a中 b -> a
*
* @param water
* @return
*/
public static boolean bToaWater(WaterStatus water) {
int a = water.getA();
int b = water.getB();
if (b == 0 || a == A_CONTAINER) {
return false;
}
if (a + b > A_CONTAINER) {
water.setA(A_CONTAINER);
water.setB(a + b - A_CONTAINER);
} else {
water.setB(0);
water.setB(a + b);
}
return true;
}
/**
* 倒出a中的水 a ->
*
* @param water
* @return
*/
public static boolean aEmpty(WaterStatus water) {
if (water.getA() == 0) {
return false;
}
water.setA(0);
return true;
}
/**
* 倒出b中的水 b ->
*
* @param water
* @return
*/
public static boolean bEmpty(WaterStatus water) {
if (water.getB() == 0) {
return false;
}
water.setB(0);
return true;
}
/**
* 输出最终结果
*
* @param stacks
*/
public static void printStack(Stack<WaterStatus> stacks) {
System.out.println("\n============倒水问题的路径为============");
if (stacks != null) {
while (!stacks.empty()) {
System.out.print(stacks.pop() + "->");
}
System.out.println("end.");
}
System.out.println("=================结束=================\n");
}
}
涉及知识点：
java深拷贝与浅拷贝；
Stack、HashSet集合的使用；
重写HashCode和equals方法；
运行结果：
版权声明：本文为W3Chhhhhh原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。