回溯法01背包问题c++代码

回溯法是解决01背包问题的一种常见方法。具体思路是对于每个物品，选择装入或不装入背包，直到将所有物品都遍历完毕。这种方法需要遍历所有可能的情况，因此时间复杂度较高，但是可以得到最优解。

以下是一个简单的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int max_weight = 0; //最大承重量
vector<int> weights; //物品重量
vector<int> values; //物品价值
vector<bool> selected; //是否选中该物品

void backtrack(int curr_weight, int curr_value, int index) {
    if (curr_weight > max_weight) { //超过承重量，直接返回
        return;
    }
    if (index == weights.size()) { //所有物品都遍历完毕
        if (curr_value > max_value) { //更新最大价值
            max_value = curr_value;
        }
        return;
    }
    //不选该物品
    backtrack(curr_weight, curr_value, index + 1);
    //选该物品
    selected[index] = true;
    backtrack(curr_weight + weights[index], curr_value + values[index], index + 1);
    selected[index] = false; //回溯
}

int main() {
    int n; //物品数量
    cin >> n;
    cin >> max_weight;
    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        weights.push_back(w);
        values.push_back(v);
        selected.push_back(false);
    }
    backtrack(0, 0, 0);
    cout << max_value << endl;
    return 0;
}