題目：
四人進城A, B, C, D， 途中路過一座橋。此時天色已黑，過橋需要唯一的一個火把照明。同時，橋上最多可以同時過兩人。火把只能手把手傳遞。四人過橋的時間分別為：A - 1分鐘， B - 2分鐘， C - 5分鐘 和D - 10分鐘。兩人過橋，以較慢的那個人的時間為準。你覺得四人過橋所需要的最短時間是多少？
這道題真沒你想的那麼容易，答案是17分鐘，你能想到過程嗎？
問題的第一直覺解法
拿到問題第一直覺是，由於A過橋時間最短，我讓A充當回程傳遞火把的那個人，那是不是最合理呢？
如果這樣計算的話：
第一步： A和D過橋，花費10分鐘，A返回送火把，花費1分鐘；
第二步： A和C過橋，花費5分鐘，A返回送火把，花費1分鐘；
第三步： A和B過橋，花費2分鐘。
總共花費時間： 10 + 1 + 5 + 1 + 2 = 19分鐘。
那答案是不是如此簡單呢? 其實大部分人考慮問題都是憑著第一感覺，並不會去深究。
問題的分析
問題中，影響過橋總時間的有兩個因素：
- 回程送火炬的人所花費時間必須儘量短，你不可能讓C和D去傳遞火把。A是第一選擇，B是次優選擇。
- 兩人過橋，存在一個時間內耗。A和D過橋，A的速度優勢沒有被完全突出出來。反而由於一直陪著走路慢的人，而不斷加大內耗。最好的辦法是A和B一起走，C和D一起走，這樣內耗是最小的。
那麼怎麼樣才能完成這個舉動呢？我們一直想的是最佳的傳遞火炬的人是A。但是B一個來回只比A慢2分鐘，在考慮內耗的情況下，B是可以被考慮來傳遞火把的。
問題的正解
第一步： A和B過橋，花費2分鐘，A返回送火把，花費1分鐘；
第二步： C和D過橋，花費10分鐘，B返回送火把，花費2分鐘；
第三步： A和B過橋，花費2分鐘。
總共花費時間： 2 + 1 + 10 + 2 + 2 = 17分鐘。
總結
喜歡我的文章請點擊關注每天都有料的“逃學博士”。如果你有更好的解法或者想法，歡迎留言探討。
分享到:
閱讀更多 逃學博士 的文章
