wine.cpp

883分酒问题

#include<iostream>
using namespace std;
int all[10000][8];									//所有状态集
int state[7]={8,8,0,0,0,0,0};						//0，1为两8升瓶，2为3升杯，3——6为4人
int steps[100][7];									//保存状态序列
int count=0;										//记录解的个数
int num[1000];										//记录每个解的步数
int solutions[1000][100][7];						//记录每个解的状态集
int min_step=100;									//记录最少步数
int all_num=0;										//所有状态集当前的元素个数
int pour(int a,int b){								//进行a往b倾倒，返回可转移酒量，0表示非法
	int empty;										//记录b瓶内空余量或人还需要的酒的升数
	if(state[a]==0)return 0;						//a容器为空，非法操作
	if(a==b)return 0;								//a，b为同一容器，非法操作
	if(b<3){										//容器往容器
		if(b<2){									//b为8升瓶
			empty=8-state[b];						//8升瓶的空余量
		}
		else{										//b为3升瓶
			empty=3-state[b];						//3升瓶的空余量
		}	
		if(state[a]<empty)return state[a];			//a瓶内酒比b瓶空余量少
		return empty;
	}
	else{											//容器往人
		empty=4-state[b];							//人还需喝的升数
		if(state[a]>empty)return 0;					//a瓶内酒比人要喝的多，非法操作
		return state[a];
	}
}
bool isstated(int c){								//判断目前状态是否在之前出现过，未出现过就返回false，同时添加到状态集中，出现过的返回true
	int j;
	for(int i=0;i<all_num;i++)
	{
		for(j=0;j<7;j++){
			if(state[j]!=all[i][j])					//状态未出现过，跳出循环
				break;
		}
		if(j==7){									//状态出现过
			if(c<all[i][7]){						//判断是否在之前出现过，是返回true，不是则记录下该状态现在出现在第几步
				all[i][7]=c;
				return false;
			}
			else
				return true;
		}
	}
	for(int i=0;i<7;i++)							//状态未出现过，将当前状态添加到所有状态集中
		all[all_num][i]=state[i];	
	all[all_num][7]=c;								//记录下该状态出现在第几步
	all_num++;
	return false;
}

void solve(int c){
	if(state[0]==0&&state[1]==0&&state[2]==0){		//得到一个解
		count++;
		num[count]=c;								//记录该解所需步数
		for(int i=0;i<c;i++){						//将该解的每个状态保存进所有解状态集中
			for(int j=0;j<7;j++){
				solutions[count][i][j]=steps[i][j];
			}
		}
		return;										//回溯
	}
	if(isstated(c))return;							//判读状态是否出现过，出现过则回溯
	int n;
	for(int a=0;a<3;a++){							//枚举，前三个瓶开始逐一倾倒
		for(int b=0;b<7;b++){
			if((n=pour(a,b))>0){					//操作合法
				state[a]=state[a]-n;				//修改对应瓶或人的状态
				state[b]=state[b]+n;
				for(int i=0;i<8;i++){
					steps[c][i]=state[i];			//记录当前状态
				}
				solve(c+1);							//进入下一步
				state[b]=state[b]-n;				//回溯反操作
				state[a]=state[a]+n;
			}
		}
	}
}
int main()
{
	solve(0);
	int n=0;
	for(int i=1;i<=count;i++){						//寻找步数最少的解，记录下其步数和解的序号
		if(num[count]<min_step)min_step=num[count];
		n=count;
	}
	cout<<"最优解共"<<min_step<<"步："<<endl;
	for(int i=0;i<min_step;i++){					//从所有解的状态集中输出最优解的步骤
		cout<<"(";
		for(int j=0;j<6;j++){
			cout<<solutions[n][i][j]<<",";
		}
		cout<<solutions[n][i][6]<<")"<<endl;
	}
	return 0;
}