昨日在“三思小百科” http://www.oursci.org/ency/math/002.htm看到一篇好文章。该文较详细的介绍了灌水（倒酒）问题的一般解法。根据文章提示的算法，我写了一个程序。
问题和算法简介：
倒水问题的经典形式是这样的：
“假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。”
　　当然题外是有一些合理的限制的，比如从池塘里灌水的时候，不管壶里是不是已经有水了，壶一定要灌满，不能和另一个壶里的水位比照一下“毛估估”（我们可以假设壶是不透明的，而且形状也不同）；同样的，如果要把水从壶里倒进池塘里，一定要都倒光；如果要把水从一个壶里倒进另一个壶里，也要都倒光，除非在倒的过程中另一个壶已经满了；倒水的时候水没有损失（蒸发溢出什么的）等等等等。
 
算法介绍：“灌水定理”：
“如果有n个壶容积分别为A1，A2，……，An（Ai均为大于0的整数）设w为另一大于0的整数。则用此n个壶可倒出w升水的充要条件为：
　1)　w小于等于A1+A2+......+An；
　2)　w可被(A1,A2,......,An)（这n个数的最大公约数）整除。”
　这两个条件都显然是必要条件，如果1)不被满足的话，你连放这么多水的地方都没有。2)的道理和上面两个壶的情况完全一样，因为在任何步骤中，任何壶中永远只有(A1,A2,......,An)的倍数的水。

如果A1，A2，……，An是n个整数，(A1,A2,......,An)=s，那么存在整数U1，U2，……，Un，使得
　　　　　　　U1A1 + U2A2 + ...... + UnAn = s. 　　　(*)
在代数学上称此结果为“整数环是主理想环”。
回头看“灌水定理”。w是(A1,A2,......,An)的倍数，根据上节的公式(*)，两边乘以这个倍数，我们就有整数V1，V2，……，Vn使得 V1A1 + V2A2 + ...... + VnAn = w.注意到Vi是有正有负的。这就说明，只要分别把A1，A2，……，An壶，灌上V1，V2，……，Vn次（如果Vi是负的话，“灌上Vi次”要理解成“倒空-Vi次”），就可以得到w升水了。

具体操作： 先求出各Vi。然后遍历所有的壶，往Vi是正数的壶里灌水，灌1次就把Vi减1。再把这些水到进Vi是负数的壶里，等某个壶灌满了，就把它倒空，然后给这个负的Vi加1，壶之间倒来倒去不变更各Vi的值。要注意的是要从池塘里灌水，一定要用空壶灌，要倒进池塘里的水，一定要是整壶的。这样一直到所有Vi都是0为止。
注意：为了得到较优解，应先把Vi是负数的壶全部处理好，等到所有的壶都不能往池中倒水了，再把Vi是正数的壶里的水倒入Vi等于0的壶中。 

我的程序：
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h>
#define MAX 10 //所需壶的最大数量 

int Result(int cubage[], int times[], int n);
void GetElements(int cubage[], int times[], int n, int w);
void GetBest(int cubage[], int times[], int temp[], int n, int w, int top, int *min);
int IsStepEnd(int times[], int n);
void Process(int cubage[], int times[], int n);
int Sum(int cup[], int n);
int CommonDivisor(int m, int n);
int ComDiv(int cubage[], int n);

int main(void) 
{ 
    int cubage[MAX] = {0};//用来存储各壶的容积
    int times[MAX] = {0};//用来存储从池中加水（或倒水）次数，正数表示加水，负数表示倒水 
    int n; //壶的实际数量 
    int d;//存储所有壶的容积的最大公约数 
    int w;//存储最终需要的水的数量 
    int i;
    
    while (1)//可以处理多次 
    {
        puts("请输入壶的数量(输入0结束程序)");
        scanf("%d", &n);
        
        if (n == 0)//如果输入0，结束程序 
            break;
        
        puts("请输入各个壶的容积");
        for (i=0; i<n; i++)
            scanf("%d", &cubage[i]);
            
        puts("请输入最终需要的水的数量");
        scanf("%d", &w);
        
        d = ComDiv(cubage, n);//获取所有壶的容积的最大公约数 
        
        if (Sum(cubage, n) < w || w % d != 0)//如果不满足条件，则无解 
        {
            puts("NO");
            continue;
        }
        
        //获取各个壶从池中加水（或倒水）次数，times[i]>0表示从池中加水；times[i]<0表示往池中倒水 
        GetElements(cubage, times, n, w);
        for (i=0; i<n; i++)
            printf("%d: %d\n", cubage[i], times[i]);
            
        Process(cubage, times, n);//输出详细操作过程 
    }
        
      system("pause");
      return 0; 
}

void GetElements(int cubage[], int times[], int n, int w)
{
    int temp[MAX] = {0};//用来存储中间结果
    int min = 200; //存储最少的操作次数，初始化为200（假设操作次数不超过200） 
    
    GetBest(cubage, times, temp, n, w, 0, &min); 
}

//计算U1A1 + U2A2 + ...... + UnAn 
int Result(int cubage[], int times[], int n)
{
    int sum = 0;
    int i;
    
    for (i=0; i<n; i++)
        sum += times[i] * cubage[i];
        
    return sum;
}

//求满足 ∑times[i] * cubage[i] = w的最佳times[]
void GetBest(int cubage[], int times[], int temp[], int n, int w, int top, int *min)
{    
    int i, sum;
    
    if (top == n)
    {
        if (Result(cubage, temp, n) == w)//如果满足条件 
        {
            sum = Sum(temp, n);//计算加（倒）水次数之和 
            if (sum < *min)//取加（倒）水次数之和最小的结果作为最佳结果（意味着操作次数最少） 
            {
                for (i=0; i<n; i++)//存储最佳结果 
                    times[i] = temp[i];
                *min = sum;
            }
        }
    }
    else//回溯寻找最佳结果 
    {
        for (i=-50; i<51; i++)
        {
            temp[top] = i;//存储中间过程 
            GetBest(cubage, times, temp, n, w, top+1, min);
        }
    }
}

int IsEnd(int times[], int n)//判断是否已经处理完毕，处理完毕返回1，否则返回0 
{
    int i;
    
    for (i=0; i<n; i++)//当所有的times[i] == 0时，表示处理完毕 
    {
        if (times[i] != 0)
            return 0;
    }
    
    return 1;
}

int IsStepEnd(int times[], int n)//判断是否已经把该倒水的壶处理完毕，处理完毕返回1，否则返回0 
{
    int i;
    
    for (i=0; i<n; i++)//当所有的times[i] >= 0时，表示所有的壶都不再往池中倒水 
    {
        if (times[i] < 0)
            return 0;
    }
    
    return 1;
}

void Process(int cubage[], int times[], int n)//输出详细操作过程 
{
    int water[MAX] = {0};//存储各个壶当前的储水量 
    int count = 0;//累计操作次数 
    int need, fact;//need表示当前壶需要加入的水量，fact表示当前壶实际加入的水量 
    int i, j, k;
    
    //输出表头 
    printf("step: ");
    for (j=0; j<n; j++)
        printf("c[%d] ", j);
    for (j=0; j<n; j++)
        printf("t[%d] ", j);
    printf("\n");
    printf("step: ");
    for (j=0; j<n; j++)
        printf("%3d  ", cubage[j]);
    for (j=0; j<n; j++)
        printf("%3d  ", times[j]);
    printf("\n\n");
                    
    while (!IsStepEnd(times, n))//一直处理，直到已经把该倒水的壶处理完毕 
    {
        for (i=0; i<n; i++)//遍历数组，进行从池中加水和倒水操作 
        {
            if (water[i] == 0 && times[i] > 0)//若当前壶空，且仍可以进行加水操作，则从池中加水 
            {
                water[i] = cubage[i];
                --times[i];
                //输出操作步骤 
                printf("%4d: ", ++count);
                for (j=0; j<n; j++)
                    printf("%3d  ", water[j]);
                for (j=0; j<n; j++)
                    printf("%3d  ", times[j]);
                printf("\n");
            }
            if (water[i] == cubage[i] && times[i] < 0)//若当前壶满，且仍可以进行倒水操作，则往池中倒水
            {
                water[i] = 0;
                ++times[i];
                //输出操作步骤     
                printf("%4d: ", ++count);
                for (j=0; j<n; j++)
                    printf("%3d  ", water[j]);
                for (j=0; j<n; j++)
                    printf("%3d  ", times[j]);
                printf("\n");
            }
        }
        //遍历数组，壶之间倒来倒去，以调整各壶的储水量 
        for (i=0; !IsStepEnd(times, n) && i<n; i++)
        {  
            if (times[i] < 0)//如果当前壶仍可以进行倒水操作，则从别的壶倒水给它，等它满后就可往池中倒水了 
            {
                for (j=0; j<n; j++)//遍历所有的壶，寻找可以倒水给cup[i]的壶，注意：可倒多次 
                {
                    need = cubage[i] - water[i];//计算cup[i]需要加入的水量 
                    if (need == 0)//如果不需要加水，退出循环 
                        break;
                    
                    if (times[j] >= 0)//cup[j]不能往池中倒水了，可以把它的水倒给cup[i] 
                    {
                        fact = water[j] < need ? water[j] : need;//计算cup[i]实际加入的水量
                        water[i] += fact;
                        water[j] -= fact;
                        
                        if (fact > 0)//如果真的进行了倒水操作，则输出该过程 
                        {
                            printf("%4d: ", ++count);
                            for (k=0; k<n; k++)
                                printf("%3d  ", water[k]);
                            for (k=0; k<n; k++)
                                printf("%3d  ", times[k]);
                            printf("\n");
                        }
                    }
                }
            } 
        }
    }
    
    while (!IsEnd(times, n))//一直操作直至结束 
    {
        for (i=0; i<n; i++)//遍历数组，进行从池中加水操作 
        {
            if (water[i] == 0 && times[i] > 0)//若当前壶空，且仍可以进行加水操作，则从池中加水 
            {
                water[i] = cubage[i];
                --times[i];
                //输出操作步骤 
                printf("%4d: ", ++count);
                for (j=0; j<n; j++)
                    printf("%3d  ", water[j]);
                for (j=0; j<n; j++)
                    printf("%3d  ", times[j]);
                printf("\n");
            }
        }
        //遍历数组，壶之间倒来倒去，以调整各壶的储水量 
        for (i=0; !IsEnd(times, n) && i<n; i++)
        {  
            if (times[i] == 0)//cup[i]不能从池中取水和倒水了，可以把其他壶中的水倒给它
            {
                for (j=0; j<n; j++)//遍历所有的壶，寻找可以倒水给cup[i]的壶，注意：可倒多次 
                {
                    need = cubage[i] - water[i];//计算cup[i]需要加入的水量 
                    if (need == 0)//如果不需要加水，退出循环 
                        break;
                    
                    if (times[j] > 0)//若cup[j]可以从池中取水，则把它的水倒给cup[i] 
                    {
                        fact = water[j] < need ? water[j] : need;//计算cup[i]实际加入的水量
                        water[i] += fact;
                        water[j] -= fact;
                        
                        if (fact > 0)//如果真的进行了倒水操作，则输出该过程 
                        {
                            printf("%4d: ", ++count);
                            for (k=0; k<n; k++)
                                printf("%3d  ", water[k]);
                            for (k=0; k<n; k++)
                                printf("%3d  ", times[k]);
                            printf("\n");
                        }
                    }
                }
            } 
        }
    }
}

//对所有壶的容积或加（倒）水次数求和
int Sum(int cup[], int n)
{
    int sum = 0;
    int i;
    
    for (i=0; i<n; i++)
        sum += abs(cup[i]);//注意因为times[]的元素值有正有负，故累计次数时应取绝对值 
    
    return sum;
}

//返回m,n的最大公约数 
int CommonDivisor(int m, int n)
{
    int temp;
    
    while (n > 0)
    {
        temp = m % n;
        m = n;
        n = temp;
    }
    return m;
}

//返回所有壶的容积的最大公约数
int ComDiv(int cubage[], int n)
{
    int d = cubage[0];
    int i;
    
    for (i=1; i<n; i++)
        d = CommonDivisor(d, cubage[i]);
    
    return d;
}

评论