过桥
问题:
有四个人需要在漆黑的夜晚过一个破旧的木桥，不幸的是，破旧的桥最多只能支持2个人同时过桥，而由于是在夜晚他们需要使用仅有的一个手电筒才能安全过桥，并且每个人过桥的时间也是不同的，分别是 1分钟，2分钟，7分钟和10分钟。请问四个人全部安全通过这座桥最短需要多长时间？
答案：
最直接的思路应是让过桥最快的人作为领航员带领每个人一起过桥，这样需要多少时间呢？
10 + 1 + 7 + 1 + 2 =21分钟。
真的是这样吗？当然不是，不然也太简单了。
让我们头脑风暴一下，为了减少过桥总时间，我们应该让10 和 7同时过桥，如果他们同时过桥，那需要其中的一个返回去接剩下的人（送手电筒）。
这明显不是我们想要的结果，很奇怪我们为什么会这么想？ 也许我们可以让 1 先等在那边，然后把手电筒带回来。
哈哈，这已经非常接近答案了！
最快的办法就是让 1 过桥并返回，然后让2作为导航员再把1带领过桥。
整体策略就出来了：
- 1 和 2过桥，2 返回
- 7 和 10 过桥，1 返回
- 1 和 2一起过桥 (结束)
合计时间 = 2 + 2 + 10 + 1 + 2 = 17 分钟
推荐阅读
更多
获取更多内容请关注微信公众号豆志昂扬:
- 直接添加公众号豆志昂扬；
-
微信扫描下图二维码；
