經典智力面試題：一家人過橋
以下文章來源於小 K 算法 ，作者小 K 算法
[
曾就職華爲和美團，中山大學數學與計算機系本科，專注分享數學、算法、科學等硬核知識](#)
0****1
故事起源
小明一家人過橋，現在是黑夜，所以必須要有燈。小明過橋要 1 秒，弟弟要 3 秒，爸爸要 6 秒，媽媽要 8 秒，爺爺要 12 秒。
此橋每次最多可過 2 人，過橋速度依最慢者而定，燈在點燃後 30 秒就會熄滅。
請問小明一家應如何過橋？
02
思考
只有一盞燈，所以一個人過橋肯定不行，他還得把燈送回來。
那肯定得兩個人一起過橋，同時還有一個人返回把燈送回來。
因爲小明的耗時是最少的，那我們的第一想法就是由小明來拿燈並返回，分別和其它 4 人一起過橋。
03
小明拿燈
第一次，小明和弟弟一起過橋用 3 秒，返回 1 秒，還剩 26 秒。
第二次，小明和爸爸一起過橋用 6 秒，返回 1 秒，還剩 19 秒。
第三次，小明和媽媽一起過橋用 8 秒，返回 1 秒，還剩 10 秒。
第四次，因爲爺爺要用 12 秒，時間不夠，已經無法過橋了。那我們就要切換思路，還有沒有更好的方法呢？
04
調整思維
先把每個人的耗時用圖形展示出來，更直觀。
可以把過橋想象成一個運輸的過程，每次運輸最大容量爲 2 個矩形。
假設小明和爺爺組合，或者媽媽和爺爺組合如下：
因爲一定是以最慢的爲準，也就是以最長的矩形爲準，可以發現小明和爺爺組合浪費了很多空間，而媽媽和爺爺組合就浪費的比較少。這就啓示儘量讓運輸效率更高，也就是浪費的空間越少越好。
05
抽象描述
有 5 個長度不一的木塊，現在要用箱子裝下所有的木塊，每個箱子最多裝 2 個，箱子的寬度等於所裝的最大木塊的寬度，怎樣裝可以讓所有箱子的寬度總和最小？
你品，你細品，如果不考慮返回送燈，是不是就很像上面的過橋問題。通過這種抽象描述，應該很多同學有一種熟悉的感覺。
是的，你沒有猜錯，是不是很像動態規劃裏面的多個揹包啊。
不過這個問題還用不到動態規劃，用貪心的思想即可，儘量讓相等的放一起，就可以浪費更少的空間。
06
回到之前的問題
根據上面的思想，讓耗時相等的儘量一起。
第一次，小明和弟弟一起過橋用 3 秒，小明返回 1 秒，還剩 26 秒。
第二次，媽媽和爺爺一起過橋用 12 秒，弟弟返回 3 秒，還剩 11 秒。
第三次，小明和爸爸一起過橋用 6 秒，小明返回 1 秒，還剩 4 秒。
第四次，小明和弟弟一起過橋用 3 秒，還有 1 秒。
小明一家人安全過橋，perfect。
07
總結
這類智力面試題，可以先嚐試自己的第一感覺，如果不對就切換思路，思維不能侷限，很快就可以發現規律了。
如果喜歡小 K 的文章，請點個關注，分享給更多的人，小 K 將持續更新，謝謝啦!
本文原創作者：小 K，一個思維獨特的寫手。
文章首發平臺：微信公衆號【小 K 算法】。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/DUqCLjP5vNyxokwipvP2lA