經典算法題：四人過橋問題的 Java 實現與最優解分析

問題背景

在漆黑的夜晚，四位旅行者來到一座狹窄且無護欄的橋邊。他們只有一支手電筒，且橋面一次僅能容納兩人通行。四人單獨過橋所需時間分別為 1、2、5、10 分鐘；兩人同行時，以較慢者的速度為準。如何設計方案，使四人在最短時間內全部過橋？

最優策略分析

直覺上讓最快的人（1 分鐘）反复送手電筒似乎合理，但實際上並非最優。關鍵在於讓最慢的兩人（5 和 10 分鐘）一起過橋，避免他們分別拖慢總時間。最優步驟如下：

1. 1 和 2 分鐘者過橋（耗時 2 分鐘），1 分鐘者送回手電筒（+1 分鐘）
2. 5 和 10 分鐘者過橋（耗時 10 分鐘），2 分鐘者送回手電筒（+2 分鐘）
3. 1 和 2 分鐘者再次過橋（耗時 2 分鐘）

總耗時：2 + 1 + 10 + 2 + 2 = 17 分鐘，這是理論最小值。

Java 代碼實現

以下為基於 JDK 1.3 的模擬實現，輸出每一步動作與累計時間：

public class BridgeCrossing {
    public static void main(String[] args) {
        int[] time = {1, 2, 5, 10};
        boolean[] onLeft = {true, true, true, true}; // true 表示在左岸
        int totalTime = 0;
        int direction = 1; // 1: 左->右, 0: 右->左

        while (onLeft[0] || onLeft[1] || onLeft[2] || onLeft[3]) {
            if (direction == 1) { // 過橋
                direction = 0;
                if (onLeft[0] && onLeft[1]) { // 策略：先讓 1 和 2 過
                    System.out.println(time[0] + " 分鐘者過橋");
                    System.out.println(time[1] + " 分鐘者過橋");
                    totalTime += time[1];
                    onLeft[0] = onLeft[1] = false;
                } else { // 讓 5 和 10 過
                    System.out.println(time[2] + " 分鐘者過橋");
                    System.out.println(time[3] + " 分鐘者過橋");
                    totalTime += time[3];
                    onLeft[2] = onLeft[3] = false;
                }
                System.out.println("累計時間 = " + totalTime);
            } else { // 送手電筒回來
                direction = 1;
                if (!onLeft[0]) { // 1 分鐘者在右岸，由他送回
                    onLeft[0] = true;
                    System.out.println(time[0] + " 分鐘者送回手電筒");
                    totalTime += time[0];
                } else { // 否則由 2 分鐘者送回
                    onLeft[1] = true;
                    System.out.println(time[1] + " 分鐘者送回手電筒");
                    totalTime += time[1];
                }
                System.out.println("累計時間 = " + totalTime);
            }
        }
        System.out.println("全部過橋完成，總耗時：" + totalTime + " 分鐘");
    }
}

運行結果

1 分鐘者過橋
2 分鐘者過橋
累計時間 = 2
1 分鐘者送回手電筒
累計時間 = 3
5 分鐘者過橋
10 分鐘者過橋
累計時間 = 13
2 分鐘者送回手電筒
累計時間 = 15
1 分鐘者過橋
2 分鐘者過橋
累計時間 = 17
全部過橋完成，總耗時：17 分鐘

擴展思考

此問題屬於經典的「贪心算法」與「狀態空間搜索」範疇。若人數增多或時間不固定，可改用 BFS 或 Dijkstra 算法在狀態圖中尋找最短路徑。代碼中硬編碼的策略僅適用於此特定數據；通用解法需建立狀態類，並用優先隊列進行最優搜索。