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

#define MAX_N 100  // 最大集装箱数量 
int n;              // 集装箱数
int boxArr[MAX_N];  // 集装箱重量数组
int C1;             // 第一艘轮船的载重量
int currWeight = 0; // 当前载重量
int bestWeight = 0; // 当前最优载重量
int bestx[MAX_N];   // 最佳装入数组 当前最优解 
int x[MAX_N];       // 装入数组 当前解

void backtrace(int i, int leftWeight) {//i集装箱索引，leftWeight剩余重量
    // 1. 到达叶节点
    if (i >= n) { // i此时的值=叶节点+1
        if (currWeight > bestWeight) { 
            for (int j = 0; j < n; j++) // 记录当前最佳解
                bestx[j] = x[j]; 
            bestWeight = currWeight;
        }
        return;
    } 
    // 剪枝1：如果当前背包重量加上剩余的重量都无法超过当前最优解，直接返回
    if (currWeight + leftWeight <= bestWeight) {  return;  } 
    // 2. 搜索左子树：选择装入第i个集装箱
    if (currWeight + boxArr[i] <= C1) { // x[i] = 1
        x[i] = 1;
        currWeight += boxArr[i];
        backtrace(i + 1, leftWeight - boxArr[i]);  // 递归时更新剩余重量
        currWeight -= boxArr[i];  // 回溯时撤销选择
    } 
    // 3. 搜索右子树：不装入第i个集装箱
    // 剪枝2：如果当前背包容量加上剩余集装箱总重量仍然无法找到更好的解，返回
    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; // 第一艘轮船的载重量  
    int totalWeight = 0;
    for (int i = 0; i < n; i++) {// 设置集装箱重量，并计算总重量
        boxArr[i] = boxes[i];
        totalWeight += boxArr[i];
    } 
    // 调用回溯算法
    backtrace(0, totalWeight); 
    // 输出最优方案
    printf("当前最优方案:\n");
    for (int i = 0; i < n; i++) {
        printf("%d: %d\n", boxArr[i], bestx[i]);
    }
    printf("最优解：%d\n", bestWeight); 
    return 0;
}