過橋
問題:
有四個人需要在漆黑的夜晚過一個破舊的木橋，不幸的是，破舊的橋最多只能支持2個人同時過橋，而由于是在夜晚他們需要使用僅有的一個手電筒才能安全過橋，并且每個人過橋的時間也是不同的，分別是 1分鐘，2分鐘，7分鐘和10分鐘。請問四個人全部安全通過這座橋最短需要多長時間？
答案：
最直接的思路應是讓過橋最快的人作為領航員帶領每個人一起過橋，這樣需要多少時間呢？
10 + 1 + 7 + 1 + 2 =21分鐘。
真的是這樣嗎？當然不是，不然也太簡單了。
讓我們頭腦風暴一下，為了減少過橋總時間，我們應該讓10 和 7同時過橋，如果他們同時過橋，那需要其中的一個返回去接剩下的人（送手電筒）。
這明顯不是我們想要的結果，很奇怪我們?yōu)槭裁磿@么想？ 也許我們可以讓 1 先等在那邊，然后把手電筒帶回來。
哈哈，這已經非常接近答案了！
最快的辦法就是讓 1 過橋并返回，然后讓2作為導航員再把1帶領過橋。
整體策略就出來了：
- 1 和 2過橋，2 返回
- 7 和 10 過橋，1 返回
- 1 和 2一起過橋 (結束)
合計時間 = 2 + 2 + 10 + 1 + 2 = 17 分鐘
推薦閱讀
更多
獲取更多內容請關注微信公眾號豆志昂揚:
- 直接添加公眾號豆志昂揚；
-
微信掃描下圖二維碼；
