01背包问题回溯法c++

好的，以下是一个简单的 01 背包问题的回溯法的 C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

int max_value = 0; // 最大价值
int n, c; // 物品数量和背包容量
vector<int> w, v; // 物品重量和价值

void backtrack(int index, int cur_weight, int cur_value) {
    if (index == n) { // 达到最后一个物品，更新最大价值
        max_value = max(max_value, cur_value);
        return;
    }
    if (cur_weight + w[index] <= c) { // 选择当前物品
        backtrack(index + 1, cur_weight + w[index], cur_value + v[index]);
    }
    backtrack(index + 1, cur_weight, cur_value); // 不选择当前物品
}

int main() {
    cin >> n >> c;
    w.resize(n);
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    backtrack(0, 0, 0);
    cout << max_value << endl;
    return 0;
}

这个代码使用递归函数 `backtrack` 来实现回溯法。在每一个节点，我们有两种选择：选择当前物品或不选择当前物品。我们用 `cur_weight` 和 `cur_value` 来记录当前已经选择的物品的重量和价值。如果当前的重量已经超过了背包容量 `c`，我们就不再往下搜索。如果当前的物品已经是最后一个物品，我们就更新最大价值 `max_value` 并返回。

回溯法的时间复杂度是指数级别的，所以对于大规模的问题，回溯法可能不是最优的算法。但对于小规模的问题，回溯法是一种简单而有效的解决方法。