容器取水

发表于 更新于 分类于 ，

一个经典的问题：使用容量为3升和5升的水桶取出4升的水，只可以进行如下操作： - 装满任意一个水桶； - 清空任意一个水桶； - 从一个水桶向另外一个水桶倒水，直到装满或者倒空；

方法为：5升桶装满>>>倒到3升桶>>>3升桶倒掉>>>5升桶剩下的2升倒到3升桶>>>5升桶装满>>>5升桶往装着2升水的3升桶倒入1升>>>3升桶的水倒掉。最后在5升桶中还剩下4升水。

把这个问题推广到更普遍的形式：有两个水壶，容量分别为 Capacity 1和 Capacity 2升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。倒水操作和之前所述一致。

（lc365）

暴力遍历

使用BFS暴力枚举各种情况，枚举过程需要记录已经出现过的水总量，遍历到已出现过的总量略过，到最后队列为空还未出现目标总量则说明无法取到相应容量的水。（开始时两个桶总量无法达到目标值则不可能达到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def canMeasureWater(Capacity1: int, Capacity2: int, targetCapacity: int) -> bool:
    queue = deque()
    queue.append((0, 0))
    exists = set()
    while queue:
        n = len(queue)
        for _ in range(n):
            temp = queue.popleft()
            if temp[0] == targetCapacity or temp[1] == targetCapacity or temp[0] + temp[1] == targetCapacity:
                return True
            exists.add(temp)
            if (0, temp[1]) not in exists:
                queue.append((0, temp[1]))
            if (temp[0], 0) not in exists:
                queue.append((temp[0], 0))
            if (jug1Capacity, temp[1]) not in exists:
                queue.append((jug1Capacity, temp[1]))
            if (temp[0], jug2Capacity) not in exists:
                queue.append((temp[0], jug2Capacity))
            f1t2 = (max(temp[0] + temp[1] - jug2Capacity, 0), min(jug2Capacity, temp[0] + temp[1]))
            if f1t2 not in exists:
                queue.append(f1t2)
            f2t1 = (min(jug1Capacity, temp[0] + temp[1]), max(0, temp[0] + temp[1] - jug1Capacity))
            if f2t1 not in exists:
                queue.append(f2t1)
    return False

迭代遍历

观察规律可以发现，可以通过不断使用小桶倒水，大桶加水的方式来得到新的水总量。即设大桶容量为a小桶容量为b，初始可得a+b的水，通过小桶不断倒水，可以获取a-b,a-2b...a-kb的水，当水总量不足小桶容量时，往大桶加水，又可以得出2a-kb,2a-(k+1)b...最终我们可以获取ma-nb的水，当ma等于nb等于a和b的最小公倍数时，水总量为0，即将进入下一个循环，所以在此期间为找到目标水量，则无法得到目标水量。

1
2
3
4
5
6
7
8
9
10
11
12
def canMeasureWater(x: int, y: int, z: int) -> bool:
    a = min(x,y)
    b = max(x,y)
    c = a + b
    while c:
        if c==z:
            return True
        if c>=b:
            c -= b
        else:
            c += a
    return False

数学推导

我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。证明：

首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的； 其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满； 再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。 因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a, b，使得\(ax+by=z\)

而只要满足 \(z\leq x+y\)，且这样的 a, b存在，那么我们的目标就是可以达成的。这是因为：

若 \(a\geq 0, b\geq 0\)，那么显然可以达成目标。

若$ a< 0$，那么可以进行以下操作：

  • 往 y 壶倒水；

  • 把 y 壶的水倒入 x 壶；

  • 如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。

重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。

若 \(b\lt 0\)，方法同上，x 与 y 互换。

而贝祖定理告诉我们，\(ax+by=z\)有解当且仅当 z 是 x, y的最大公约数的倍数。因此我们只需要找到 x, y 的最大公约数并判断 z 是否是它的倍数即可。

1
2
3
4
5
6
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
    if x + y < z:
        return False
    if x == 0 or y == 0:
        return z == 0 or x + y == z
    return z % math.gcd(x, y) == 0