怎么用一个容量为 3 公斤的桶和一个容量 5 公斤的桶称量出 4 公斤量的水？

题目：怎么用一个容量为 3 公斤的桶和一个容量 5 公斤的桶称量出 4 公斤量的水？

分析

设两个桶分别为 A 和 B，容量分别为 M 和 N。目标为任一桶的当前盛水容量为 G。

开始状态： 两个桶均为空。

过程： 桶没有刻度，针对这两个桶每次所能完成的动作只能是以下 6 种之一：

• 把 A 桶的水清空；
• 把 B 桶的水清空；
• 把 A 装潢水；
• 把 B 装满水；
• 把 A 的水倒入 B；
• 把 B 的水倒入 A。

结束状态： 其中一个桶装入的水容量为 G。

完整过程： 从开始状态开始，每次可以选择一个动作之一，然后判断是否到达结束状态。

很显然，从开始到结束的这些状态，应该构成一个图。图的顶点就是各个状态，图的边就是动作之一。 我们要做的，就是从图的开始状态顶点找到所有能到达结束状态顶点的所有路径。我相信你的脑海里面已经构造出这个图了。

通常，我们把这种问题称作是关于图的状态空间搜索问题，而采用的算法则可以是广度优先搜索。

实现

下面开始写算法实现，不要忘记广度优先搜索算法怎么写就好。

Go Playground: https://play.golang.org/p/_xK0_vOvmQi

package main

import "fmt"

// State 状态，构成图的顶点
type State struct {
	// A、B 两桶当前装水的容量
	a, b int

	// 遍历时记录父顶点，即记住路径
	parent *State

	// 所作的动作
	action string
}

const (
	// M 为 A 桶的最大容量
	M = 3
	// N 为 B 桶的最大容量
	N = 5
	// G 为想要得到的容量
	G = 4
)

const (
	actionFillA      = `Fill A`
	actionFillB      = `Fill B`
	actionClearA     = `Clear A`
	actionClearB     = `Clear B`
	actionFillAWithB = `Fill A With B`
	actionFillBWithA = `Fill B With A`
)

var (
	// A 桶的范围是 [0,M]，B 桶的范围是 [0,N]
	// 所以去重后的状态总数是 (M+1)*(N+1)
	maxStates = (M + 1) * (N + 1)

	// 状态集合。
	states = make([]*State, 0, maxStates)

	// 已访问的状态。
	// 这里用一维数组，方便初始化
	visited = make([]bool, maxStates)
)

// 把未访问过的状态加入到待遍历队列
func tryAddState(a, b int, parent *State, action string) {
	p := (N+1)*a + b
	if visited[p] {
		return
	}

	states = append(states, &State{
		a:      a,
		b:      b,
		parent: parent,
		action: action,
	})

	visited[p] = true
}

// 到达结束状态时递归回溯并显示出路径
func backtrace(s *State) {
	if s != nil {
		backtrace(s.parent)
		fmt.Printf("(%d,%d) %s\n", s.a, s.b, s.action)
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	// 加入开始状态，准备广度优先搜索遍历
	tryAddState(0, 0, nil, `Initialize`)

	// 遍历所有状态（不要使用 range，因为 range 是立即求值）
	for i := 0; i < len(states); i++ {
		s := states[i]

		// 如果到达结束条件
		if s.a == G || s.b == G {
			// 回溯并输出当前路径
			backtrace(s)
			fmt.Println()
			continue
		}

		// 如果没达到结束条件，把当前顶点的所有出度加入列表

		tryAddState(0, s.b, s, actionClearA)
		tryAddState(s.a, 0, s, actionClearB)
		tryAddState(M, s.b, s, actionFillA)
		tryAddState(s.a, N, s, actionFillB)

		// A 最多可以给 B 的量
		t1 := min(s.a, N-s.b)
		// B 最多可以给 A 的量
		t2 := min(s.b, M-s.a)

		tryAddState(s.a+t2, s.b-t2, s, actionFillAWithB)
		tryAddState(s.a-t1, s.b+t1, s, actionFillBWithA)
	}

	fmt.Printf("Processed %d states\n", len(states))
}

运行输出结果：

(0,0) Initialize
(0,5) Fill B
(3,2) Fill A With B
(0,2) Clear A
(2,0) Fill A With B
(2,5) Fill B
(3,4) Fill A With B

(0,0) Initialize
(3,0) Fill A
(0,3) Fill B With A
(3,3) Fill A
(1,5) Fill B With A
(1,0) Clear B
(0,1) Fill B With A
(3,1) Fill A
(0,4) Fill B With A

Processed 16 states

可以看到，总共有 2 种答案。

参考

• 两个杯子，一个盛三升水、一个盛四升水，要得到两升水，怎么用 C 语言求解？ - Milo Yip的回答 - 知乎