c++回溯法解决装载问题

装载问题是一个经典的NP完全问题，回溯法是解决该问题的一种常用方法。下面是使用C++实现的装载问题回溯法解法：

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

const int MAXN = 20; // 最大物品数量
int n; // 物品数量
int c; // 载重量
int w[MAXN + 1]; // 每个物品的重量
int cw; // 当前载重量
int bestw; // 最佳载重量
int r; // 剩余物品重量和
vector<int> path; // 当前路径

void BackTrack(int i) {
    if(i > n) { // 到达叶子节点
        if(cw > bestw) {
            bestw = cw;
        }
        return;
    }
    r -= w[i];
    if(cw + w[i] <= c) { // 选第i件物品
        path.push_back(i);
        cw += w[i];
        BackTrack(i + 1);
        cw -= w[i];
        path.pop_back();
    }
    if(cw + r > bestw) { // 不选第i件物品
        BackTrack(i + 1);
    }
    r += w[i];
}

int main() {
    cin >> n >> c;
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        r += w[i];
    }
    BackTrack(1);
    cout << bestw << endl;
    for(int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    return 0;
}

上述代码中，我们使用了一个全局变量`path`来记录当前路径，每次找到更优的解时，更新`bestw`并更新`path`。函数`BackTrack`实现回溯搜索，其中`i`表示当前搜索到的物品编号，`cw`表示当前载重量，`r`表示剩余物品重量和，当`i>n`时表示搜索到了叶子节点，即所有物品都已考虑完毕。在每个节点处，我们分别考虑选或不选当前物品，根据剩余物品重量和`r`与当前载重量`cw`的比较，可以进行剪枝，从而减少搜索时间。

该算法的时间复杂度为$O(2^n)$，因此对于物品数量较大的情况，可能会出现超时的情况。