深搜算法：倒油/面向对象的思想来做
【摘要】 题目：有一位厨师要从盛12斤油（a桶）的桶中倒出6斤油来，可是手边只有盛8斤油（b桶）和盛5斤油（c桶）的两个桶，问如何操作才能将6斤取出来呢？
下面为JAVA实现代码： 主类：
package cn.hncu.oil.dfs1;
import cn.hncu.oil.common.Bucket;
import cn.hncu.oil.common.DumpCa...
题目：有一位厨师要从盛12斤油（a桶）的桶中倒出6斤油来，可是手边只有盛8斤油（b桶）和盛5斤油（c桶）的两个桶，问如何操作才能将6斤取出来呢？
下面为JAVA实现代码：
主类：
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()); } }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
DumpCase 类：
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; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
Bucket 类：
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; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
Myset 类：
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; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。
原文链接：chenhx.blog.csdn.net/article/details/50870978
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）