Massive Algorithms: Mother's Milk

Mother's Milk - USACO 1.4.4

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in)

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

http://mangogao.com/read/89.html
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。
写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

http://jusaco.blogspot.com/2013/07/mothers-milk-training.html
X. DFS
http://www.icycandy.com/blog/usaco-1-4-4-mothers-milk
https://tausiq.wordpress.com/2010/11/26/usaco-mothers-milk/

设res[j]为C桶中牛奶量为j的可能性

status[i][j]为A桶有i牛奶,C桶有j牛奶的可能性,初态为i==0;j==C;

当i==0时置res[j]=true;

总共有六种倒法A->B,A->C,B->A,B->C,C->A,C->B

对每种status,分别搜索这六种倒法.

http://leonlu.iteye.com/blog/1125500

用DFS解。用searched[x][y]数组记录搜索过的状态，不使用三维数组是因为前2维决定了第三维。用amount[z]的布尔值记录当x=0时z的值。


	private static boolean[][] searched = new boolean[21][21];
	private static boolean[] amount = new boolean[21];
	private static int a,b,c;

	public static void main(String[] args) throws Exception{
	BufferedReader in = new BufferedReader(new FileReader("milk3.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("milk3.out")),true);

	//read data
	StringTokenizer st = new StringTokenizer(in.readLine());
	a = Integer.parseInt(st.nextToken());
	b = Integer.parseInt(st.nextToken());
	c = Integer.parseInt(st.nextToken());
	dfs(0,0,c);
	for (int i = 0;i < c;i++)
	if (amount[i])
	out.print(i + " ");
	out.println(c);

	System.exit(0);
	}

	private static void dfs(int x, int y, int z){
	if(searched[x][y]) return;
	searched[x][y] = true;
	if(x == 0) amount[z] = true;
	if (x>0 && y<b)
	dfs(max(0,x+y-b),min(b,x+y),z);
	if (x>0 && z<c)
	dfs(max(0,x+z-c),y,min(c,x+z));
	if (y>0 && x<a)
	dfs(min(a,y+x),max(0,y+x-a),z);
	if (y>0 && z<c)
	dfs(x,max(0,y+z-c), min(c,y+z));
	if (z>0 && x<a)
	dfs(min(a,z+x),y,max(0,z+x-a));
	if (z>0 && y<b)
	dfs(x,min(b,z+y),max(0,z+y-b));
	}

bool res[21]={0};
bool status[21][21]={0}; //status[i][j]表示A有i牛奶，C有j牛奶的可能
int a,b,c,p,q;
 
int main()
{
    ifstream fin("milk3.in");
    ofstream fout("milk3.out");
 
    int s=0,i,j=0;
    fin>>a>>b>>c;
    search(0,c);
 
    for (i=0;i<=20;i++) if (res[i]) s++;
    for (i=0;i<=20;i++)
    {
        if (res[i])
        {
            fout<<i;
            j++;
            if (j==s) fout<<endl;
            else fout<<’ ‘;
        }
    }
 
    fin.close();
 
    fout.close();
 
    return 0;
}
 
void search(int ma,int mc)
{
    if (status[ma][mc]) return;
 
    int mb=c-ma-mc;
    status[ma][mc]=true;
    if (ma==0) res[mc]=true;
 
    search(ma-min(ma,b-mb),mc); //a->b
    search(ma-min(ma,c-mc),mc+min(ma,c-mc)); //a->c
    search(ma+min(mb,a-ma),mc); //b->a
    search(ma,mc+min(mb,c-mc)); //b->c
    search(ma+min(a-ma,mc),mc-min(a-ma,mc)); //c->a ma + min(mc,a-ma),
    search(ma,mc-min(b-mb,mc)); //c->b
}

X. BFS
http://qingtangpaomian.iteye.com/blog/1635111

用BFS逐层产生可能有的A,B,C三个桶的牛奶数量。如果已经产生过了则不用进入bfs的队列了，所以我们用一个hash表记录所有已经产生的状态。

如果bfs的队列当中没有元素了，则程序结束，输出所有已经产生的结果。

public static void main(String[] args) {
try {
Scanner in = new Scanner(new BufferedReader(new FileReader("milk3.in")));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("milk3.out")));
LinkedList<status> list = new LinkedList<status>();//bfs队列
HashSet<status> hash = new HashSet<status>();//记录已经产生过的a,b,c三个桶的容量状态
HashSet<Integer> result = new HashSet<Integer>();//记录已经产生的c桶的状态
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
status init = new status(0,0,c);
list.add(init);
while (list.size()!=0){//编列bfs队列
status temp = list.remove(0);
if (hash.contains(temp)){
//doNothing
} else {
hash.add(temp);
//如果a桶的容量为空，则在结果集当中加入c的状态
if (temp.a==0){
result.add(temp.c);
}
//遍历所有可能的倒牛奶方式
//a->b
if (temp.a >= b-temp.b){
status node = new status(temp.a-b+temp.b,b,temp.c);
if (!hash.contains(node)){
list.add(node);
}
}else{
status node = new status(0,temp.b+temp.a,temp.c);
if (!hash.contains(node)){
list.add(node);
}
}
//a->c
if (temp.a >= c-temp.c){
status node = new status(temp.a-c+temp.c,temp.b,c);
if (!hash.contains(node)){
list.add(node);
}
}else{
status node = new status(0,temp.b,temp.c+temp.a);
if (!hash.contains(node)){
list.add(node);
}
}
//b->a
if (temp.b >= a-temp.a){
status node = new status(a,temp.b-a+temp.a,temp.c);
if (!hash.contains(node)){
list.add(node);
}
}else{
status node = new status(temp.a+temp.b,0,temp.c);
if (!hash.contains(node)){
list.add(node);
}
}
//b->c
if (temp.b >= c-temp.c){
status node = new status(temp.a,temp.b-c+temp.c,c);
if (!hash.contains(node)){
list.add(node);
}
}else {
status node = new status(temp.a,0,temp.c+temp.b);
if (!hash.contains(node)){
list.add(node);
}
}
//c->a
if (temp.c >= a-temp.a){
status node = new status(a,temp.b,temp.c-a+temp.a);
if (!hash.contains(node)){
list.add(node);
}
}else{
status node = new status(temp.a+temp.c,temp.b,0);
if (!hash.contains(node)){
list.add(node);
}
}
//c->b
if (temp.c >= b-temp.b){
status node = new status(temp.a,b,temp.c-b+temp.b);
if (!hash.contains(node)){
list.add(node);
}
}else {
status node = new status(temp.a,temp.b+temp.c,0);
if (!hash.contains(node)){
list.add(node);
}
}
}
}
Integer[] out = new Integer[result.size()];
result.toArray(out);
Arrays.sort(out);
StringBuilder sb = new StringBuilder();
for (int i = 0;i<out.length;i++){
sb.append(out[i]+" ");
}
sb.deleteCharAt(sb.length()-1);
pw.println(sb);
pw.close();
in.close();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
class status {
int a ;
int b ;
int c ;
public status(int a ,int b ,int c){
this.a = a;
this.b = b;
this.c = c;
}
@Override
public boolean equals(Object obj) {
status sta = (status)obj;
if (this.a == sta.a && this.b == sta.b && this.c == sta.c){
return true;
} else {
return false;
}
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return a*1 + b*2 + c*3;
}
}

http://jackneus.com/programming-archives/mothers-milk/

Read full article from mother'smilk - codetrick

Mother's Milk - USACO 1.4.4

PROGRAM NAME: milk3

INPUT FORMAT

SAMPLE INPUT (file milk3.in)

OUTPUT FORMAT

SAMPLE OUTPUT (file milk3.out)

SAMPLE INPUT (file milk3.in)

SAMPLE OUTPUT (file milk3.out)

Labels

Popular Posts