回溯算法--装载问题

回溯算法是一种解决问题的算法思想，它通过不断地尝试所有可能的解决方案来寻找问题的最优解。而装载问题是回溯算法的一个经典应用，它是指在给定一些集装箱和一艘载重量为C的轮船的情况下，如何将这些集装箱装载到轮船上，使得轮船的载重量最大。

具体来说，装载问题可以通过回溯算法来解决。我们可以定义一个递归函数来尝试所有可能的装载方案，每次递归时，我们可以选择将当前集装箱装载到轮船上或者不装载，然后继续递归下去。当所有集装箱都被考虑过后，我们就可以得到一个装载方案，然后比较这个方案的载重量和当前最优解的载重量，如果更优则更新最优解。

下面是一个简单的装载问题的回溯算法实现：

#include <stdio.h>

#define MAX_N 100

int n; // 集装箱数量
int c; // 轮船载重量
int w[MAX_N]; // 集装箱重量
int best[MAX_N]; // 当前最优解
int cur[MAX_N]; // 当前解
int cur_weight; // 当前载重量
int best_weight; // 当前最优解的载重量

void backtrack(int i) {
    if (i == n) { // 所有集装箱都被考虑过
        if (cur_weight > best_weight) { // 更新最优解
            best_weight = cur_weight;
            for (int j = 0; j < n; j++) {
                best[j] = cur[j];
            }
        }
        return;
    }
    if (cur_weight + w[i] <= c) { // 装载当前集装箱
        cur[i] = 1;
        cur_weight += w[i];
        backtrack(i + 1);
        cur_weight -= w[i];
    }
    cur[i] = 0; // 不装载当前集装箱
    backtrack(i + 1);
}

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    backtrack(0);
    printf("最大载重量为：%d\n", best_weight);
    printf("装载方案为：");
    for (int i = 0; i < n; i++) {
        if (best[i]) {
            printf("%d ", i + 1);
        }
    }
    printf("\n");
    return 0;
}

在这个实现中，我们使用了一个数组`cur`来记录当前的解，使用`cur_weight`来记录当前的载重量，使用`best`来记录当前最优解，使用`best_weight`来记录当前最优解的载重量。在回溯函数`backtrack`中，我们首先判断是否可以装载当前集装箱，如果可以则装载，然后递归下去；如果不可以则不装载，然后递归下去。当所有集装箱都被考虑过后，我们就可以得到一个装载方案，然后比较这个方案的载重量和当前最优解的载重量，如果更优则更新最优解。