最优装载问题回溯法c++

以下是最优装载问题的回溯法C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

int n; // 集装箱数量
int c; // 轮船载重量
vector<int> w; // 集装箱重量
vector<int> cw; // 当前载重量
vector<int> bestw; // 最优载重量
int r; // 剩余集装箱重量

void backtrack(int i) {
    if (i > n) { // 到达叶节点
        if (cw[n] > bestw[n]) { // 更新最优解
            for (int j = 1; j <= n; j++) {
                bestw[j] = cw[j];
            }
        }
        return;
    }
    r -= w[i]; // 选择第i个集装箱
    if (cw[i - 1] + w[i] <= c) { // 搜索左子树
        cw[i] = cw[i - 1] + w[i];
        backtrack(i + 1);
    }
    r += w[i]; // 不选第i个集装箱
    if (cw[i - 1] + r > bestw[i - 1]) { // 搜索右子树
        cw[i] = cw[i - 1];
        backtrack(i + 1);
    }
}

int main() {
    cout << "请输入集装箱数量和轮船载重量：" << endl;
    cin >> n >> c;
    w.resize(n + 1);
    cw.resize(n + 1);
    bestw.resize(n + 1);
    r = 0;
    cout << "请输入每个集装箱的重量：" << endl;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        r += w[i];
    }
    backtrack(1);
    cout << "最优载重量为：" << bestw[n] << endl;
    return 0;
}