过河问题 - 最少时间算法及代码实现 - 常规

过河问题 - 最少时间算法及代码实现

在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一座独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。

现输入 n（2 < n < 100）和这 n 个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有 3 个人甲、乙、丙，他们单独过桥的时间分别为 1、2、4，则总共最少需要的时间为 7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸并将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为 2 + 1 + 4 = 7。

代码实现

#include <iostream>
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE];
bool pos[SIZE];

int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

int go(bool stage) {
    int i, j, num, tmp, ans;
    if (stage == RIGHT_TO_LEFT) {
        num = 0;
        ans = 0;
        for (i = 1; i <= n; i++)
            if (pos[i] == RIGHT) {
                num++;
                if (hour[i] > ans)
                    ans = hour[i];
            }
        if (num <= 0)
            return ans;
        ans = INFINITY;
        for (i = 1; i <= n - 1; i++)
            if (pos[i] == RIGHT)
                for (j = i + 1; j <= n; j++)
                    if (pos[j] == RIGHT) {
                        pos[i] = LEFT;
                        pos[j] = LEFT;
                        tmp = max(hour[i], hour[j]);
                        if (tmp < ans)
                            ans = tmp;
                        pos[i] = RIGHT;
                        pos[j] = RIGHT;
                    }
        return ans;
    }
    if (stage == LEFT_TO_RIGHT) {
        ans = INFINITY;
        for (i = 1; i <= n; i++)
            if (pos[i] != LEFT) {
                pos[i] = RIGHT;
                tmp = go(RIGHT_TO_LEFT) + hour[i];
                if (tmp < ans)
                    ans = tmp;
                pos[i] = LEFT;
            }
        return ans;
    }
    return 0;
}

int main() {
    int i;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> hour[i];
        pos[i] = RIGHT;
    }
    cout << go(RIGHT_TO_LEFT) << endl;
    return 0;
}

代码解析

go(bool stage)函数: 该函数根据传入的stage参数来判断当前是向左过河 (RIGHT_TO_LEFT) 还是向右过河 (LEFT_TO_RIGHT)。
RIGHT_TO_LEFT: 表示从右岸到左岸。代码中，首先计算右岸所有人的最大过桥时间，如果没人需要过桥，直接返回最大时间。否则，遍历所有在右岸的人，将他们两两组合过桥，比较组合过桥时间，取最小值。
LEFT_TO_RIGHT: 表示从左岸到右岸。代码中，遍历所有在左岸的人，将他们分别过桥，比较过桥时间，取最小值。
main()函数: 输入人数 n 和每个人过桥时间，调用 go(RIGHT_TO_LEFT) 函数计算总的最小时间。

关键步骤分析

num<=0: 该判断用于检查右岸是否还有人需要过桥，如果没有人需要过桥，则直接返回最大过桥时间。
pos[i] != LEFT: 该判断用于检查当前遍历的人是否在左岸，如果在左岸，则将其过桥并计算新的最小时间。

注: 该代码使用了递归的思想，在 LEFT_TO_RIGHT 状态下，每次都调用 go(RIGHT_TO_LEFT) 函数来计算从右岸到左岸的最短时间。

总结

过河问题是一个经典的算法问题，它体现了递归和贪心算法的思想。通过分析代码和关键步骤，可以更深入地理解算法的原理，并将其应用到其他问题中。