回溯法解决01背包问题c++

可以使用递归和回溯法来解决01背包问题。以下是一个C++实现的例子：

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

int max_weight = 0; // 最大重量
vector<int> items; // 物品重量
vector<int> value; // 物品价值

void backtrack(int i, int current_weight, int current_value, int n, int w) {
    if (current_weight > w) { // 当前重量超过背包容量，直接返回
        return;
    }
    if (i == n) { // 所有物品已经尝试完
        if (current_value > max_weight) { // 更新最大价值
            max_weight = current_value;
        }
        return;
    }
    // 不选择当前物品
    backtrack(i + 1, current_weight, current_value, n, w);
    // 选择当前物品
    backtrack(i + 1, current_weight + items[i], current_value + value[i], n, w);
}

int main() {
    int n, w;
    cin >> n >> w; // 输入物品数量和背包容量
    items.resize(n);
    value.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> items[i] >> value[i]; // 输入每个物品的重量和价值
    }
    backtrack(0, 0, 0, n, w); // 回溯搜索
    cout << max_weight << endl; // 输出最大价值
    return 0;
}

在回溯过程中，我们通过选择或不选择当前物品来探索所有可能的情况。如果当前重量超过背包容量，直接返回；如果所有物品已经尝试完，更新最大价值并返回。