题目：有一位厨师要从盛12斤油（a桶）的桶中倒出6斤油来，可是手边只有盛8斤油（b桶）和盛5斤油（c桶）的两个桶，问如何操作才能将6斤取出来呢？
下面为JAVA实现代码： 主类：
代码语言：javascript复制package cn.hncu.oil.dfs1;
import cn.hncu.oil.common.Bucket;
import cn.hncu.oil.common.DumpCase;
import cn.hncu.oil.common.Myset;
public class DumpOilDFS {
public static void main(String[] args) {
Bucket buckets[] = new Bucket[3];
buckets[0] = new Bucket(12, 12);
buckets[1] = new Bucket(8, 0);
buckets[2] = new Bucket(5, 0);
DumpCase u = new DumpCase(buckets);
Myset caseset = new Myset();
caseset.add(u);
dfs(u,caseset);
}
private static void dfs(DumpCase u0, Myset caseset) {
for(Bucket bucket: u0.getBucket()){
if(bucket.getNow()==6){
//System.out.println("find a case");
print(u0);
return;
}
}
int n = u0.getBucket().length;//桶的个数
DumpCase u = new DumpCase(u0);
//用备份节点去搜
//遍历所有的DumpCase: 依次让桶i向j倒
for(int i=0;i<n;i ){
for(int j=0;j<n;j ){
if(i==j){//不能自己给自己的桶倒油
continue;
}
//算出桶i给j倒时，能倒多少-->temp
int temp = u.getBucket()[i].canOut();
if(u.getBucket()[j].canIn()<u.getBucket()[i].canOut()){
temp = u.getBucket()[j].canIn();
}
//倒油
u.getBucket()[i].out(temp);
u.getBucket()[j].in(temp);
//判断该情况是否已经出现过了//如果存在，要还原(把油倒回去)
if(caseset.contains(u)){
u.getBucket()[i].in(temp);
u.getBucket()[j].out(temp);
continue;
}
DumpCase v = new DumpCase(u);
v.setParent(u0);
caseset.add(v);
//System.out.println(a);
dfs(v,caseset);
u.getBucket()[i].in(temp);
u.getBucket()[j].out(temp);
}
}
}
private static void print(DumpCase u0) {
Myset set =new Myset();
set.add(u0);
DumpCase v =u0.getParent();
while(v!=null){
set.add(v);
//System.out.println(v.getBucket()[0].getNow() "," v.getBucket()[1].getNow() "," v.getBucket()[2].getNow());
v= v.getParent();
}
System.out.println("------------");
//System.out.println("12,0,0");
Object objs[] = set.getAll();
for(int i=objs.length-1;i>=0;i--){
DumpCase u =(DumpCase) objs[i];
System.out.println(u.getBucket()[0].getNow() "," u.getBucket()[1].getNow() "," u.getBucket()[2].getNow());
}
}
}DumpCase 类：
代码语言：javascript复制package cn.hncu.oil.common;
import java.util.Arrays;
public class DumpCase {
Bucket buckets[];
DumpCase parent = null;
public DumpCase(){
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result Arrays.hashCode(buckets);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DumpCase other = (DumpCase) obj;
if (!Arrays.equals(buckets, other.buckets))
return false;
return true;
}
public DumpCase(Bucket buckets[]){
this.buckets = buckets;
}
public DumpCase(DumpCase u) {//必须要深拷贝
this.buckets = new Bucket[u.getBucket().length];
for(int i=0;i<u.getBucket().length;i ){
this.buckets[i] = new Bucket(0, 0);
this.buckets[i].max=u.buckets[i].max;
this.buckets[i].now=u.buckets[i].now;
}
}
public Bucket[] getBucket() {
return buckets;
}
public void setBucket(Bucket[] buckets) {
this.buckets = buckets;
}
public DumpCase getParent() {
return parent;
}
public void setParent(DumpCase parent) {
this.parent = parent;
}
}Bucket 类：
代码语言：javascript复制package cn.hncu.oil.common;
public class Bucket {//桶的容量和现在装的油的多少
int now;
int max;
public Bucket(int max,int now) {
this.max=max;
this.now=now;
}
public void in(int n){
now =n;
}
public void out(int n){
now-=n;
}
public int getNow() {
return now;
}
public int getMax() {
return max;
}
public int canIn(){
return max-now;
}
public int canOut(){
return now;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result max;
result = prime * result now;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Bucket other = (Bucket) obj;
if (max != other.max)
return false;
if (now != other.now)
return false;
return true;
}
}Myset 类：
代码语言：javascript复制package cn.hncu.oil.common;
public class Myset {
private Object[] objs = new Object[0];
public boolean contains(Object obj){
for(Object objtemp:objs){
if(objtemp.equals(obj)){
return true;
}
}
return false;
}
public boolean add(Object obj){
if(contains(obj)){
return false;
}
Object[] objstemp = new Object[objs.length 1];
System.arraycopy(objs, 0, objstemp, 0, objs.length);
objstemp[objs.length]=obj;
objs = objstemp;
return true;
}
public Object[] getAll(){
return objs;
}
public int Size(){
return objs.length;
}
}
