没有明白为什么是x = Math.min(a, 3 - b)？

Question

/**
 * 说明：由5升和3升的桶，如何倒出4升的水出来?
 */
function findPath() {
	let pre = Array(100).fill(-1);
	let target = -1;

	function bfs() {
		let queue = [];
		let visited = Array(100).fill(false);

		queue.push(0);
		visited[0] = true;

		while (queue.length != 0) {
			let v = queue.shift();
			let a = (v / 10) | 0;
			let b = v % 10;

			let nexts = [];
			//a,3：装满b
			nexts.push(a * 10 + 3);
			//5,b：装满a
			nexts.push(5 * 10 + b);
			//a,0：倒掉b
			nexts.push(a * 10 + 0);
			//0,b：倒掉a
			nexts.push(0 * 10 + b);

			//! a倒向b, 只有2中情况，情况1：要么完全装下a(倒入a), 情况2：要么装满溢出(倒入3-b)
			//! 情况1：b能完全装下a
			let s1 = a;
			nexts.push((a - s1) * 10 + Math.min(b + s1, 3));

			//! 情况2：装满溢出(倒入3-b)
			let s2 = 3 - b;
			if (a - s2 >= 0) {
				//! 说明：得确保a此时能有s2的水
				nexts.push((a - s2) * 10 + Math.min(b + s2, 3));
			}

			//! b倒向a, 只有2中情况，情况1：要么完全装下b(倒入b), 情况2：要么装满溢出(倒入5-a)
			//! 情况1：a能完全装下b
			let s3 = b;
			nexts.push(Math.min(a + b, 5) * 10 + (b - s3));

			//! 情况2：装满溢出(倒入5-a)
			let s4 = 5 - a;
			if (b - s4 > 0) {
				nexts.push(Math.min(a + s4, 5) * 10 + (b - s4));
			}

			for (const next of nexts) {
				if (!visited[next]) {
					queue.push(next);
					visited[next] = true;
					pre[next] = v;
					if (((next / 10) | 0) === 4 || next % 10 === 4) {
						console.error("find solution:", next);
						target = next;
						return;
					}
				}
			}
		}
	}

	bfs();

	if (target !== -1) {
		let cur = target;
		let path = [];
		while (cur !== 0) {
			path.push(cur);
			cur = pre[cur];
		}
		path.push(0);
		return path.reverse();
	} else {
		return -1;
	}
}

以上是我自己的理解，没有明白为什么可以是x = Math.min(a, 3 - b)

Answer 1

liuyubobobo 2023-02-19 14:43:11

x = min(a, 3 - b) 中的 x 表示，能从 5 升的桶中倒出多少水。

其中 a 表示，现在 5 升的桶中有多少水。3 - b 表示 3 升的水中最多可以装多少水。

最终从 5 升的桶中倒出的水量，是这二者的最小值。

继续加油！：）

• 提问者 Potter520 #1

  明白了，a表示表示5升的桶里水量，3-b 表示3升桶最多可倒的水量。假如：a>3-b, 那么只能往3升桶里倒3-b升水；假如：a<3-b, 那么最多往3升桶里倒a升水。 最终简化就是x=min(a,3-b)。感谢老师回复