经典智力面试题：一家人过桥-轻识

来源 | 小K算法（ID：xiaok365）

故事起源

小明一家人过桥，现在是黑夜，所以必须要有灯。小明过桥要1秒，弟弟要3秒，爸爸要6秒，妈妈要8秒，爷爷要12秒。
此桥每次最多可过2人，过桥速度依最慢者而定，灯在点燃后30秒就会熄灭。
请问小明一家应如何过桥？

思考

只有一盏灯，所以一个人过桥肯定不行，他还得把灯送回来。

那肯定得两个人一起过桥，同时还有一个人返回把灯送回来。

因为小明的耗时是最少的，那我们的第一想法就是由小明来拿灯并返回，分别和其它4人一起过桥。

小明拿灯

第一次，小明和弟弟一起过桥用3秒，返回1秒，还剩26秒。

第二次，小明和爸爸一起过桥用6秒，返回1秒，还剩19秒。

第三次，小明和妈妈一起过桥用8秒，返回1秒，还剩10秒。

第四次，因为爷爷要用12秒，时间不够，已经无法过桥了。那我们就要切换思路，还有没有更好的方法呢？

调整思维

先把每个人的耗时用图形展示出来，更直观。

可以把过桥想象成一个运输的过程，每次运输最大容量为2个矩形。

假设小明和爷爷组合，或者妈妈和爷爷组合如下：

因为一定是以最慢的为准，也就是以最长的矩形为准，可以发现小明和爷爷组合浪费了很多空间，而妈妈和爷爷组合就浪费的比较少。这就启示尽量让运输效率更高，也就是浪费的空间越少越好。

抽象描述

有5个长度不一的木块，现在要用箱子装下所有的木块，每个箱子最多装2个，箱子的宽度等于所装的最大木块的宽度，怎样装可以让所有箱子的宽度总和最小？
你品，你细品，如果不考虑返回送灯，是不是就很像上面的过桥问题。通过这种抽象描述，应该很多同学有一种熟悉的感觉。
是的，你没有猜错，是不是很像动态规划里面的多个背包啊。