c语言回溯算法装载问题

装载问题是指有n个集装箱要装上一艘重量为W的轮船，重量用数组w【】表示。不考虑体积限制，先要从这些集装箱中选出重量和小于等于W并且尽可能大的若干装上船。这是一个经典的回溯算法问题，下面是C语言实现的代码：

#include <stdio.h>
#define MAXN 30
int n, W;
int w[MAXN], cw, bestw; // cw表示当前已经装载的重量，bestw表示最优装载重量
int r[MAXN]; // r[i]表示剩余物品重量的和，从第i个物品开始往后的所有物品重量和
void backtrack(int i)
{
    if (i > n) // 到达叶节点
    {
        if (cw > bestw) bestw = cw; // 更新最优解
        return;
    }
    r[i] = r[i + 1] + w[i]; // 计算剩余物品重量和
    if (cw + w[i] <= W) // 装入第i个物品
    {
        cw += w[i];
        backtrack(i + 1);
        cw -= w[i];
    }
    if (r[i] > bestw) // 不装入第i个物品
    {
        backtrack(i + 1);
    }
}
int main()
{
    printf("请输入集装箱数量n和轮船重量W：");
    scanf("%d%d", &n, &W);
    printf("请输入每个集装箱的重量：");
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
    }
    for (int i = n; i >= 1; i--)
    {
        r[i] = r[i + 1] + w[i];
    }
    backtrack(1);
    printf("最大装载重量为：%d\n", bestw);
    return 0;
}