if(size[b]-result[b]>=result[a]){
result[b]+=result[a];
result[a]=0;
}else{
//a酒杯减去b酒杯的剩余容量
result[a]-=(size[b]-result[b]);
//b酒杯装满
result[b]=size[b];
}
return true;
}
//将当前状态添加到记录中
private void addHistory(){
String his=result[0]+","+result[1]+","+result[2];
history.add(his);
}
//当前状态是否存在于历史记录中
private boolean isInHistory(){
//待优化，可以用位运算
String his=result[0]+","+result[1]+","+result[2];
return history.contains(his);
}
//添加过程
private void addCourse(){
for(int i=0;i
}
}
//移除过程
private void removeCourse(){
int length=course.size();
for(int i=length-1;i>length-4;i--){
course.remove(i);
}
}
//当前结果是否是最终结果了
private boolean isLast(){
for(int i=0;i
}
return false;
}
//输出最终结果
private void outputCourse(){
for(int i=0;i
if(i%3==2){
System.out.println(course.get(i));
}else{
System.out.print(course.get(i)+",");
}
}
System.out.println("========================");
}
}
}
import java.util.ArrayList;
import java.util.List;
public class ys_10 {
//分酒
public static void main(String[] args) {
new ys_10().new answer(12,8,5,12,0,0,6);
}
private class answer{
//保存每一次的结果
private int[] result=new int[3];
//最终存在的数字
private int last=0;
//初始大小
//历史记录
private List history=new ArrayList();
//过程
private List course=new ArrayList();
public answer(int a1,int a2,int a3,int a4,int a5,int a6,int a7){
size[0]=a1;
size[1]=a2;
size[2]=a3;
result[0]=a4;
result[1]=a5;
result[2]=a6;
last=a7;
//添加初始记录
addHistory();
addCourse();
process();
}
public void process(){
if(isLast()){
//输出结果
outputCourse();
return;
}
int one,two,three;
one=result[0];
two=result[1];
three=result[2];
int[] temp={1,2,0,2,0,1};
for(int i=0;i<6;i++){
//六种情况分别为：A->B,A->C,B->A,B->C,C->A,C->B
if(!move(i/2,temp[i])){
//移动失败
continue;
}
//是否存在该记录-》存在
if(isInHistory()){
//恢复原来的状态
result[0]=one;
result[1]=two;
result[2]=three;
//这里的剪枝很重要，否则会一直搜索下去
continue;
}else{
addHistory();
//添加有效记录
addCourse();
}
//处理下一层
process();
//应该恢复到原来状态
result[0]=one;
result[1]=two;
result[2]=three;
removeCourse();
}
}
//通过a杯装满b杯
public boolean move(int a,int b){
//a酒杯是空酒杯
if(result[a]==0)return false;
//b酒杯是满酒杯
if(result[b]==size[b])return false;
//b酒杯的剩余空间大于等于a酒杯的
if(size[b]-result[b]>=result[a]){
result[b]+=result[a];
result[a]=0;
}else{
//a酒杯减去b酒杯