四人过桥

问题描述

有四个人需要在夜间过桥，过桥时必须携带手电筒。他们只有一个手电筒，手电筒必须由人携带过桥。他们单独过桥的时间分别为[1, 2, 5, 10]分钟，两人同行时以较慢者的速度为准。桥每次最多只能承受2个人。问：如何在最短的时间内让所有人都过桥？

解决方案

你可能先想到这种方案：[1, 2]过桥 1返回 [1, 5]过桥 1返回 [1, 10]过桥，总共用时19分钟。
这种方案始终让最快的人往返传递手电筒，希望每次过桥都是最短时间，但是这种方案还有优化空间。

考虑下面两个问题：
可以节约最慢的两人的过桥时间吗？可以，让他们一起过桥，把上面的第3步改成[5, 10]过桥。
第3步结束后，桥的另一头有[2, 5, 10]，谁带回手电筒？第二快的人带回手电筒，把第4、5步改成2返回 [1, 2]过桥。也就是说需要最快的两人交替传递手电筒。
于是就有了一个方案：[1, 2]过桥 1返回 [5, 10]过桥 2返回 [1, 2]过桥，总共用时17分钟。

这里有一个演示动画：