A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「River Crossing」.

River Crossing #

Problem #

Four people, A, B, C and D need to get across a river. The only way to cross the river is by an old bridge, which holds at most 2 people at a time. Being dark, they can’t cross the bridge without a torch, of which they only have one. So each pair can only walk at the speed of the slower person. They need to get all of them across to the other side as quickly as possible. A is the slowest and takes 10 minutes to cross; B takes 5 minutes; C takes 2 minutes; and D takes I minute. What is the minimum time to get all of them across to the other side?

Solution #

解决问题的关键在于让 A 和 B 两个人一起过桥, 并且留在对岸. 因此需要先让 C, D 中的一个人过去, 在 A 和 B 过河后再把手电筒带回来. 最优规划之一如下:

• C, D 过桥
• D 回来
• A, B 过桥
• C 回来
• C, D 过桥

总共耗时 $17$ 分钟. 把 C 和 D 的位置对换也是最优解.