解决水罐问题

Question

在阅读一些关于初步数论的课堂讲稿时，我遇到了水罐问题(带两个水壶的)问题的解决方案，其总结如下：

利用两个数的G.C.D性质，即GCD(a，b)是a和b的最小可能线性组合，因此一定数量的q只能用2 tB来度量，当且仅当Q是n*GCD(a，b)，因为Q=sA +tB：

n = a positive integer
A = capacity of jug A
B=  capacity of jug B

然后，讨论了求解的方法。

解决方案的另一个模型是将各种状态建模为一个状态空间搜索问题，就像人工智能中经常使用的那样。

我的问题是:存在哪些其他已知的方法来建模解决方案，以及如何建模？谷歌并没有吐太多。

Answer 1

严格适用于2 Jug问题

Q = A * x + B * y

你需要多少加仑。

注：q必须是Gcd(A，B)的倍数，否则没有解。如果Gcd(A，B) == 1，则对任意Q都有一个解。

1) 方法1 : 扩展欧几里得算法算法的求解速度比任何图形算法都快。

2) 方法2: --这是一种天真的方法。(注意，这可以抛出2个解决方案，您必须选择哪个更短)

这个问题可以通过repeatedly从一个桶A到另一个桶B(订单无关紧要)简单地解决，直到它填满你的want...ofcoz量，当一个桶填充物时，你把它倒空，然后继续。

    A = 3, B = 4 and Q = 2

反复填A->B

    A B
   ######
    0 0
    4 0
    1 3
    1 0
    0 1
    4 1
    2 3 <-Solution

让我们试着观察如果我们走相反的路会发生什么，填充B->A

A  B
#####
0  0
0  3
3  0
3  3
4  2 <- Solution

在这种情况下，填充B->A给出的目标状态比A->B更快

Generic N Jugs这里有一个有趣的纸

Answer 2

一个令人惊奇和有趣的方法(3罐)是通过http://en.wikipedia.org/wiki/Barycentric_coordinates_(mathematics) (真的！)，在总是辉煌的网站剪裁-结：重心坐标:一个好奇的应用程序。

Answer 3

这种类型的问题通常可以接受动态规划技术。我在运筹学课程中看到了这个具体的问题。一个好的一步一步的描述是这里.