4 个人要在夜晚过一座桥,只有一盏灯,灯最多照亮 2 个人。
- 每次最多 2 人一起过桥,用时按较慢的那个人算
- 过桥必须带灯,过桥后要有人把灯送回来(每次 1 人)
- 4 人全部到终点、灯也在终点,才算通关
- 目标:让总用时最小
⭐ 评级:1 星通关 · 2 星接近最优 · 3 星达到最优
设四人用时从小到大为 X1 ≤ X2 ≤ X3 ≤ X4
方案一(最快的人来回送灯):2×X1 + X2 + X3 + X4
方案二(最慢两人一起过):X1 + 3×X2 + X4
最优时间取两者较小值
💡 小提示:当 X1 + X3 > 2×X2 时,让最慢的两个人一起过桥更划算。