题目描述
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数。 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。 写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
输入格式
单独的一行包括三个整数A,B和C。
输出格式
只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。
样例数据
input
样例输入 1
8 9 10样例输入 22 2 5 10output
样例输出 11 1 2 8 9 10
样例输出 2
2 5 6 7 8 9 10数据规模与约定
时间限制：1s
空间限制：256MB
首先分析一下题目，题目的意思是这样的：最初，A和B桶都是空的，而C桶是装满牛奶的。要找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
咋眼一看，感觉有点懵，这什么鬼啊！
再看一下题目所给的数据：1=<A,B,C<=10，由于数据量给的小，稍微想了一下，用递归暴力搜索是可行的。。。。
递归，是一个非常暴力的方法，由结论推出条件，很直观，但是需要耗费挺多的脑细胞来找递归边界。
这道题的难点就在于它的递归边界有点不好找，这也正是这道题坑的原因。
======================我是分割线======================
读完了以上废话，下面引入正题：
看一下这道题的样例：
输入样例：
SAMPLE INPUT 1
8 9 10
SAMPLE INPUT 2
2 5 10
输出样例：
SAMPLE OUTPUT 1
1 2 8 9 10
SAMPLE OUTPUT 2
5 6 7 8 9 10
样例还是给的比较良心的，让我们知道得出结果的同时还要sort排序一下（差点掉坑）。
接下来高能来袭：
仔细思考一下，如果我们要用递归来写这道题，是不是应该把所有情况列举出来，对吧！
好的，那么我们想一下：
假设A中有牛奶，那么为了枚举所有的情况，它只有两种选择
1.把牛奶倒入B 2.把牛奶倒入C。
那么问题来了，有可能牛奶倒入B倒满了，A中还有剩余。或者牛奶倒入B没有倒满，A中牛奶空了。
这两种状态是不一样的！！！！（同理A倒C）
分析一下这两种状态，可以写出A倒B的递归转移式：
if(A<=b-B) milk(0,A+B,C);
//milk表示递归函数；A,B,C表示三个桶中的牛奶剩余量，a,b,c表示三个桶的容积。 B桶还未满。
else milk(A-(b-B),b,C);
//A桶中的牛奶剩余量为（A-(b-B)）,b-B为B桶中剩余的容积。此时B桶已经满了。
同理可得A倒C，A倒B，B倒C，B倒A（与A倒B为两种不同的情况，容易混淆），C倒A（与A倒C不同），C倒B（与B倒C不同）。。
====================我是分割线===============================
递归要配合记忆化搜索，记住，递归要配合记忆化搜索。
注意要判断当前状态是否存在过。用f[A][B][C]来表示三个桶的状态
下面贴一下代码
#include<bits/stdc++.h> using namespace std; int sum[50];//sum[i]表示可能的种数 int a,b,c,p=-1; //a,b,c表示三个桶的容积 bool f[50][50][50]; void milk(int A, int B, int C)//A,B,C表示三个桶中的牛奶量 { if(f[A][B][C]) return; //记忆化搜索 f[A][B][C]=true;//布尔型数组记忆化 if(A==0) { sum[++p]=C;//情况符合，记录 } if(A<=b-B) milk(0,A+B,C);//如果a桶中的牛奶少于b桶剩余的容积，则倒入。 else milk(A-(b-B),b,C); //否则a桶剩余继续倒，把b桶倒满。 if(A<=c-C) milk(0,B,C+A);// 同理枚举a倒c。 else milk(A-(c-C),B,c); if(B<=a-A) milk(A+B,0,C); else milk(a,B-(a-A),C); if(B<=c-C) milk(A,0,C+B); else milk(A,B-(a-A),c); if(C<=a-A) milk(A+C,B, 0); else milk(a,B,C-(a-A)); if(C<=b-B) milk(A,B+C, 0); else milk(A,b,C-(b-B)); //依次枚举a,b,c桶分别有牛奶的情况，以及分别倒入另外两桶的情况全部枚举。 return; } int main() { memset(sum,0,sizeof(sum)); memset(f,0,sizeof(f)); cin>>a>>b>>c; milk(0,0,c);//表示初始状态递归 sort(sum,sum+p+1);//从把结果小到大排序 for(int i=0;i<p;i++){ cout<<sum[i]<<" ";