题目

给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。

更多详细内容，请阅读参考文档中的资料。

下面使用分支限界算法（广度优先遍历）解决本题。

Python 实现

代码：

# coding: utf8
​
_id = 0
​
​
def get_id():
    global _id
    try:
        return _id
    finally:
        _id = _id + 1
​
​
class Kettle(object):
    def __init__(self, name, total, current):
        self.name = name
        self.total = total
        self.current = current
        self.path = []
​
    @property
    def full(self):
        return self.current == self.total
​
    @property
    def remaining(self):
        return self.total - self.current
​
    @property
    def empty(self):
        return self.current == 0
​
​
def bfs(kettle1, kettle2, kettle3, wanted):
    kettles = [(kettle1, kettle2, kettle3)]
    duplicate = set()
​
    while kettles:
        k1, k2, k3 = kettles.pop(0)
        if k1.current == wanted or k2.current == wanted or k3.current == wanted:
            return k1, k2, k3
​
        for nk1, nk2, nk3 in generate_children(k1, k2, k3):
            if (nk1.current, nk2.current, nk3.current) in duplicate:
                continue
            kettles.append((nk1, nk2, nk3))
​
        for nk2, nk1, nk3 in generate_children(k2, k1, k3):
            if (nk1.current, nk2.current, nk3.current) in duplicate:
                continue
            kettles.append((nk1, nk2, nk3))
​
        for nk3, nk1, nk2 in generate_children(k3, k2, k1):
            if (nk1.current, nk2.current, nk3.current) in duplicate:
                continue
            kettles.append((nk1, nk2, nk3))
​
​
def generate_children(k1, k2, k3):
    if k1.empty:
        return
​
    # 向第二个瓶子倒
    if not k2.full:
        if k1.current >= k2.remaining:
            to_k2 = k2.remaining
        else:
            to_k2 = k1.current
        k1_current = k1.current - to_k2
        k2_current = k2.current + to_k2
​
        # 向第三个瓶子倒
        if k1_current > 0 and not k3.full:
            if k1_current >= k3.remaining:
                to_k3 = k3.remaining
            else:
                to_k3 = k1_current
​
            new_k1 = Kettle(k1.name, k1.total, k1_current - to_k3)
            new_k1.path = k1.path + [(get_id(), k1.name, k2.name, to_k2),
                                     (get_id(), k1.name, k3.name, to_k3)]
            new_k2 = Kettle(k2.name, k2.total, k2_current)
            new_k2.path = k2.path + []
            new_k3 = Kettle(k3.name, k3.total, k3.current + to_k3)
            new_k3.path = k3.path + []
            yield new_k1, new_k2, new_k3
        # 不向第三个瓶子倒
        new_k1 = Kettle(k1.name, k1.total, k1_current)
        new_k1.path = k1.path + [(get_id(), k1.name, k2.name, to_k2)]
        new_k2 = Kettle(k2.name, k2.total, k2_current)
        new_k2.path = k2.path + []
        new_k3 = Kettle(k3.name, k3.total, k3.current)
        new_k3.path = k3.path + []
        yield new_k1, new_k2, new_k3
​
    # 向第三个瓶子倒
    if not k3.full:
        if k1.current >= k3.remaining:
            to_k3 = k3.remaining
        else:
            to_k3 = k1.current
​
        new_k1 = Kettle(k1.name, k1.total, k1.current - to_k3)
        new_k1.path = k1.path + [(get_id(), k1.name, k3.name, to_k3)]
        new_k2 = Kettle(k2.name, k2.total, k2.current)
        new_k2.path = k2.path + []
        new_k3 = Kettle(k3.name, k3.total, k3.current + to_k3)
        new_k3.path = k3.path + []
        yield new_k1, new_k2, new_k3
​
    # 不向第三个瓶子倒
    new_k1 = Kettle(k1.name, k1.total, k1.current)
    new_k1.path = k1.path + []
    new_k2 = Kettle(k2.name, k2.total, k2.current)
    new_k2.path = k2.path + []
    new_k3 = Kettle(k3.name, k3.total, k3.current)
    new_k3.path = k3.path + []
    yield new_k1, new_k2, new_k3
​
​
def test():
    ok1 = Kettle("Kettle-1", 8, 8)
    ok2 = Kettle("Kettle-2", 5, 0)
    ok3 = Kettle("Kettle-3", 3, 0)
​
    d = {}
    d[ok1.name] = ok1.current
    d[ok2.name] = ok2.current
    d[ok3.name] = ok3.current
​
    k1, k2, k3 = bfs(ok1, ok2, ok3, 4)
​
    for _, from_kettle, to_kettle, number in sorted(k1.path + k2.path + k3.path, key=lambda t: t[0]):
        d[from_kettle] = d[from_kettle] - number
        d[to_kettle] = d[to_kettle] + number
   &nnbsp;    state = "%s：%d/%d，%s：%d/%d，%s：%d/%d" % (
            ok1.name,
            d[ok1.name],
            ok1.total,
            ok2.name,
            d[ok2.name],
            ok2.total,
            ok3.name,
            d[ok3.name],
            ok3.total)
        print("从 %s 向 %s 倒 %d 升，当前状态是：%s" % (from_kettle, to_kettle, number, state))
​
​
if __name__ == "__main__":
    test()

运行结果：

从 Kettle-1 向 Kettle-2 倒 5 升，当前状态是：Kettle-1：3/8，Kettle-2：5/5，Kettle-3：0/3
从 Kettle-2 向 Kettle-3 倒 3 升，当前状态是：Kettle-1：3/8，Kettle-2：2/5，Kettle-3：3/3
从 Kettle-3 向 Kettle-1 倒 3 升，当前状态是：Kettle-1：6/8，Kettle-2：2/5，Kettle-3：0/3
从 Kettle-2 向 Kettle-3 倒 2 升，当前状态是：Kettle-1：6/8，Kettle-2：0/5，Kettle-3：2/3
从 Kettle-1 向 Kettle-2 倒 5 升，当前状态是：Kettle-1：1/8，Kettle-2：5/5，Kettle-3：2/3
从 Kettle-2 向 Kettle-3 倒 1 升，当前状态是：Kettle-1：1/8，Kettle-2：4/5，Kettle-3：3/3

参考文档

• https://blog.csdn.net/u013256816/article/details/100146674