---
description: "1,2,5,10 过桥最少 17 分钟；每送走最慢两人比一次 $2b$ 与 $a+c$，两行 DP 与穷举逐一吻合"
---

# 过桥问题：1、2、5、10 分钟

## 题

夜里 4 个人要过一座桥，单程各需 1、2、5、10 分钟。桥一次最多走两人，只有一个手电筒，过桥必须打着手电，两人同行按慢者速度。手电不能扔，只能有人拿回来。最少多少分钟全部过桥？

## 一句话

**17 分钟**——关键一步是让 5 和 10 **同行**，两个最慢的人共用一次 10 分钟；直觉上的"最快者来回护送"要 19 分钟。

## 关键技巧

手电每次过去两人、回来一人，所以 $n$ 人需要 $n-1$ 次去、$n-2$ 次回。能优化的只有两件事——**慢的人尽量搭伙过**，**回程尽量由快的人跑**。

把人按速度排好 $a \le b \le \cdots \le c \le d$，每一轮只处理当前最慢的两人 $c, d$，两种送法：

- **策略 A：$a$ 护送**。$a$ 带 $d$ 过去、$a$ 回来；$a$ 带 $c$ 过去、$a$ 回来。耗时 $d + a + c + a = 2a + c + d$。
- **策略 B：慢者同行**。$a, b$ 过去、$a$ 回来；$c, d$ 过去、$b$ 回来。耗时 $b + a + d + b = a + 2b + d$。

两式都有 $a + d$，差别只剩

$$
\text{A} - \text{B} = (a + c) - 2b
$$

**$2b < a + c$ 时选 B，否则选 A。** B 付出的代价是 $b$ 多跑两趟，换来的是 $c$ 不用单独过桥、$a$ 少回一趟。

每轮送走两人后，剩下的还是同一结构的子问题。于是有两行 DP（$f(k)$ 表示最快的 $k$ 人全部过桥的最少时间，$t_1 \le \cdots \le t_n$）：

$$
f(k) = \min\bigl(f(k-1) + t_1 + t_k,\ \ f(k-2) + t_1 + 2t_2 + t_k\bigr), \quad f(1) = t_1,\ f(2) = t_2
$$

第一项是 A 的单步版本（$t_1$ 送走 $t_k$ 再回来），第二项是 B。这条 DP 在 $n \le 7$ 的随机实例上与 Dijkstra 全状态穷举逐一吻合（见折叠块）。

## 解

$a, b, c, d = 1, 2, 5, 10$：$2b = 4 < a + c = 6$，选 B。

| 步 | 动作 | 耗时 | 累计 |
| --- | --- | --- | --- |
| 1 | 1、2 过桥 | 2 | 2 |
| 2 | 1 带手电回 | 1 | 3 |
| 3 | 5、10 过桥 | 10 | 13 |
| 4 | 2 带手电回 | 2 | 15 |
| 5 | 1、2 过桥 | 2 | **17** |

对照策略 A：$10 + 1 + 5 + 1 + 2 = 19$。差的 2 分钟恰好是 $(a + c) - 2b = 6 - 4$。

17 为什么不能再少：4 人要 3 次去、2 次回，3 次去程共得运过 $4 + 2 = 6$ 人次，所以**每次去程都是两人**。若 5 和 10 分在两趟，这两趟就是 15，第三趟去程至少 2，两次回程至少各 1，合计 $\ge 19$。所以两人必须同行。这一趟不可能是第一趟（之后得有 5 或 10 回程），也不可能是最后一趟（前两趟去程里 5、10 必有一人出场）——只能在中间，对岸得事先有个快的人等着把手电拿回来，这就逼出了第 1、2 步。

## 延伸

- **切换条件因人而异**：$1, 4, 5, 10$ 时 $2b = 8 > a + c = 6$，改用 A，答案 $10 + 1 + 5 + 1 + 4 = 21$。$1, 2, 3, 4$ 时 $4 = 4$，两种一样，答案 11。
- **$n$ 人贪心**：从最慢的两人开始，每轮按 $2b$ 与 $a + c$ 比较选 A 或 B，剩 3 人时 $a+b+c$，剩 2 人时 $b$。由于 $c$ 越往后越小，**一旦某轮选了 A，之后全是 A**——最优方案是"先若干轮 B，再若干轮 A"。例：$1, 2, 5, 10, 12, 20$ 两轮都选 B，得 $25 + 15 + 2 = 42$。
- **常见错误一**：以为最快的人每趟都陪着最省。只在 $b$ 相对 $a, c$ 很慢时成立。
- **常见错误二**：让慢的人回程。回程只该由最快的 $a$ 或 $b$ 跑——DP 的两种动作正是这样搭的，Rote（2002）给出了这条 DP 最优性的完整证明，下方穷举在小规模上复核。
- **桥容量 $k > 2$**：结构变了，每趟去 $k$ 人回 1 人，最优分组不再是简单的"两慢同行"，得靠 DP 或整数规划。有兴趣可以把下方 Dijkstra 的 `(1, 2)` 换成 `range(1, k+1)` 直接跑。
- **同类技巧**：只看"最慢两人怎么送"的局部交换论证，和[两个鸡蛋](two-eggs.md)的 DP 一样，都是把大问题剥成同构子问题。

??? note "数值验证"

    Dijkstra 在"对岸集合 × 手电位置"的状态图上穷举全部走法，与两行 DP 对拍：

    ```python
    import heapq, random, itertools

    def brute(ts):
        """状态 = (对岸集合 bitmask, 手电在哪岸)。每次过 1 或 2 人。"""
        n, full = len(ts), (1 << len(ts)) - 1
        dist, pq = {(0, 0): 0}, [(0, 0, 0)]
        while pq:
            d, far, side = heapq.heappop(pq)
            if far == full:
                return d
            if d > dist[(far, side)]:
                continue
            here = [i for i in range(n) if ((far >> i) & 1) == side]
            for k in (1, 2):
                for g in itertools.combinations(here, k):
                    m = sum(1 << i for i in g)
                    nf = far | m if side == 0 else far & ~m
                    nd = d + max(ts[i] for i in g)
                    if nd < dist.get((nf, 1 - side), 1e18):
                        dist[(nf, 1 - side)] = nd
                        heapq.heappush(pq, (nd, nf, 1 - side))

    def dp(ts):
        t = sorted(ts); n = len(t)
        if n == 1:
            return t[0]
        f = [0] * (n + 1)
        f[1], f[2] = t[0], t[1]
        for k in range(3, n + 1):
            f[k] = min(f[k - 1] + t[0] + t[k - 1],             # 最快者护送最慢者
                       f[k - 2] + t[0] + 2 * t[1] + t[k - 1])   # 最慢两人同行
        return f[n]

    print(brute([1, 2, 5, 10]), dp([1, 2, 5, 10]))   # 17 17
    random.seed(4)
    for _ in range(500):
        ts = [random.randint(1, 20) for _ in range(random.randint(1, 7))]
        assert brute(ts) == dp(ts), ts
    print("n<=7 随机 500 组：DP == 穷举")
    for ts in ([1, 4, 5, 10], [1, 2, 3, 4], [1, 2, 5, 10, 12, 20]):
        print(ts, dp(ts), brute(ts))
    # [1, 4, 5, 10] 21 21
    # [1, 2, 3, 4] 11 11
    # [1, 2, 5, 10, 12, 20] 42 42
    ```