题目
相对于广搜，深搜采用的过程偏向面向过程，用“特征串”去区别两种情况是否相同，（同一种搜索）在效率比面向对象要快点。
话不多说直接上代码（3个类）：
/*** 倒油---倒油问题解决的过程* @author 宋进宇*/
import java.util.ArrayList;public class PourOil {public static void main(String[] args) {OilBucket obs[] = new OilBucket[3];obs[0] = new OilBucket(12,12);obs[1] = new OilBucket(8, 0);obs[2] = new OilBucket(5, 0);//用来记录每次倒完油后，各个油桶中存在的油ArrayList<String> list = new ArrayList<String>();//把第一次的情况先记录Buckets buckets = new Buckets();buckets.setOilBuckets(obs);list.add(buckets.toString());dfs(buckets, list);//进行深搜}public static void dfs(Buckets buckets,ArrayList<String> list){//只要有一个油桶满足存在的油量是 6 就可以了for (int k = 0; k < buckets.getOilBuckets().length; k++) {if (buckets.getOilBuckets()[k].getExist()==6) {print(buckets);return ;}}Buckets temp = new Buckets(buckets);//进行倒油 把油桶i的油倒入油桶j中for (int i = 0; i < temp.getOilBuckets().length; i++) {for (int j = 0; j < temp.getOilBuckets().length; j++) {if (j==i) {//自己不给自己倒油continue;}int add = temp.getOilBuckets()[j].add(temp.getOilBuckets()[i]);//把油桶i的油倒入油桶j中//寻找该次倒油后出现的情况是否出现过//如果是第一次出现 则继续倒油 并记录if (!list.contains(temp.toString())) {temp.setParent(buckets);list.add(temp.toString());dfs(temp, list);}//能到这里说明 不是第一次出现 把油倒回去temp.getOilBuckets()[j].pourOut(temp.getOilBuckets()[i], add);}}}private static void print(Buckets buckets) {System.out.println("--------------");String str = "";while(buckets!=null){str = buckets.toString()+str;buckets = buckets.getParent();}System.out.print(str);}
}
class Buckets {private OilBucket[] oilBuckets;//用对象数组存放所有油桶private Buckets parent; //记录父节点/*** 空参构造*/public Buckets() {}/*** 拷贝对象的构造函数 ---深拷贝（解除引用赋值捆绑）* @param buckets 被拷贝的对象*/public Buckets(Buckets buckets) {if (buckets==null||buckets.oilBuckets.length==0) {return; }this.oilBuckets = new OilBucket[buckets.oilBuckets.length];for (int i = 0; i < buckets.oilBuckets.length; i++) {this.oilBuckets[i] = new OilBucket(buckets.oilBuckets[i].getVolume(), buckets.oilBuckets[i].getExist());}}/*** 获取父节点对象* @return 父节点*/public Buckets getParent() {return parent;}/*** 设置父节点* @param parent 父节点*/public void setParent(Buckets parent) {this.parent = parent;}/*** 获取油桶的集合* @return 油桶的集合*/public OilBucket[] getOilBuckets() {return oilBuckets;}/*** 设置油桶的集合* @param oilBuckets 油桶的集合*/public void setOilBuckets(OilBucket[] oilBuckets) {this.oilBuckets = oilBuckets;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Buckets other = (Buckets) obj;///以下是根据题目需求来判断是否相等/for (int i = 0; i < oilBuckets.length; i++) {//只要有一个油桶里面的油量不同 说明两个油桶集合不相同if (oilBuckets[i].getExist()!=other.getOilBuckets()[i].getExist()) {return false;}}return true;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();if (oilBuckets==null||oilBuckets.length==0) {return null;}sb.append(oilBuckets[0].getExist());for (int i = 1; i < oilBuckets.length; i++) {sb.append(","+oilBuckets[i].getExist());}sb.append("\r\n");return sb.toString();}}
class OilBucket {private int volume;// 油桶的容量private int exist;// 油桶里已有的油public OilBucket() {}/*** 构造一个油桶* @param volume 油桶的容量* @param exist 油桶里已有的油*/public OilBucket(int volume, int exist) {super();this.volume = volume;this.exist = exist;}/*** 把油桶ob中油倒入当前对象中* * @param ob 倒出油的对象* * @return 表示倒入油的数量*/public int add(OilBucket ob) {if (ob == null) {return 0;}int add = 0;if (volume>=exist+ob.exist) {add=ob.exist;exist += ob.exist;ob.exist =0;}else{add = volume-exist;ob.exist -= add;exist = volume;}return add;}/*** 把当前对象中的油倒入ob中* * @param ob 被倒入油的对象* * @return 表示倒出油的数量*/public void pourOut(OilBucket ob,int value) {if (ob==null) {return ;}exist -= value;ob.exist += value;}public int getVolume() {return volume;}public void setVolume(int volume) {this.volume = volume;}public int getExist() {return exist;}public void setExist(int exist) {this.exist = exist;}
}