#include <stdio.h>
#define MAX_N 100  // 最大集装箱数量 
int n;              // 集装箱数
int boxArr[MAX_N];  // 集装箱重量数组
int C1;             // 第一艘轮船的载重量
int currWeight = 0; // 当前载重量
int bestWeight = 0; // 当前最优载重量
int leftWeight = 0; // 剩余集装箱重量
int x[MAX_N];       // 装入数组 当前解
int bestx[MAX_N];   // 最佳装入数组 当前最优解 
void backtrace(int i) {// 回溯算法
    // 1. 到达叶节点
    if (i >= n) { // i此时的值=叶节点+1
        if (currWeight > bestWeight) {
            for (int j = 0; j < n; j++) 
                bestx[j] = x[j]; 
            bestWeight = currWeight;
        }
        return;
    }
    leftWeight -= boxArr[i];
    // 2. 搜索左子树
    if (currWeight + boxArr[i] <= C1) { // x[i] = 1
        x[i] = 1;
        currWeight += boxArr[i];
        backtrace(i + 1);
        currWeight -= boxArr[i];
    }
    // 3. 搜索右子树
    if (currWeight + leftWeight > bestWeight) {
        x[i] = 0;
        backtrace(i + 1);
    }
    leftWeight += boxArr[i];
}
int main() {
    // 初始化集装箱信息
    int boxes[] = {4, 5, 6}; 
    n = sizeof(boxes) / sizeof(boxes[0]); // 货物数量
    C1 = 10; // 第一艘轮船的载重量
    // 设置集装箱重量
    for (int i = 0; i < n; i++) {
        boxArr[i] = boxes[i];
        leftWeight += boxArr[i];  // 计算剩余集装箱重量
    }
    // 调用回溯算法
    backtrace(0);
    // 输出最优方案
    printf("当前最优方案:\n");
    for (int i = 0; i < n; i++) {
        printf("%d: %d\n", boxArr[i], bestx[i]);
    }
    printf("最优解：%d\n", bestWeight);
    return 0;
}