士兵过河问题c++完整代码

以下是士兵过河问题的 c 代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

int n;              // 士兵数量
int a[MAX_N + 1];   // 士兵位置
int b[MAX_N + 1];   // 搜索时当前状态下，右岸剩余的士兵位置
int f[MAX_N][MAX_N];    // 记忆化搜索数组，f[i][j] 表示在当前状态下，在左岸 i 到 j 区间内士兵过河最小所需时间
int ans = 1<<30;    // 当前还未得到答案，初始化为无穷大

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void dfs(int now, int t) {
    if (t >= ans) {
        return;             // t 已经大于等于最优解了，不可能得到更优的解了，直接退出
    }
    if (now > n) {
        if (t < ans) {
            ans = t;        // 得到了比当前答案更优的解
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (a[now] == b[i]) {   // 士兵在右岸，需要运回左岸
            b[i] = -1;
            dfs(now + 1, t + a[now]);
            b[i] = a[now];
        }
        else if (b[i] == -1) {  // 目标岸没有士兵，当前的士兵可以运送至目标岸，但需要检查此时在目标岸的士兵是否连续
            int j = i + 1;
            while (j <= n && b[j] == -1) {
                j++;
            }
            if (j > n || a[now] < b[j]) {   // 右岸无士兵或可以过河
                b[i] = a[now];
                dfs(now + 1, t + b[i]);
                b[i] = -1;
            }
        }
        else if (a[now] < b[i]) {   // 右岸有士兵，当前的士兵可以运送至目标岸，但需要检查此时在目标岸的士兵是否连续
            int j = i + 1;
            while (j <= n && b[j] == -1) {
                j++;
            }
            if (j > n || a[now] < b[j]) {   // 右岸无士兵或可以过河
                int temp = b[i];
                b[i] = a[now];
                dfs(now + 1, t + temp);
                b[i] = temp;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    qsort(a + 1, n, sizeof(int), cmp);
    for (int i = 1; i <= n; i++) {
        b[i] = -1;
    }
    dfs(1, 0);
    printf("%d\n", ans);

    return 0;
}

注意：这段代码仅供参考，可能并不是最优解。在写实际代码时，应注意避免使用递归，防止栈溢出。