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

下面是01背包问题的回溯算法的C++代码实现：

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

// n: 物品数量，w: 背包容量，weight: 物品重量，value: 物品价值
void backtrack(int n, int w, vector<int>& weight, vector<int>& value, int index, int& maxValue, int curWeight, int curValue)
{
    if (index == n) { // 达到叶子节点
        if (curWeight <= w && curValue > maxValue)
            maxValue = curValue; // 更新最大价值
        return;
    }

    // 不选第index个物品
    backtrack(n, w, weight, value, index + 1, maxValue, curWeight, curValue);

    // 选第index个物品
    if (curWeight + weight[index] <= w) {
        curWeight += weight[index];
        curValue += value[index];
        backtrack(n, w, weight, value, index + 1, maxValue, curWeight, curValue);
        curWeight -= weight[index];
        curValue -= value[index];
    }
}

int knapsack(int n, int w, vector<int>& weight, vector<int>& value)
{
    int maxValue = 0;
    backtrack(n, w, weight, value, 0, maxValue, 0, 0);
    return maxValue;
}

int main()
{
    int n = 5, w = 10;
    vector<int> weight = {2, 2, 6, 5, 4};
    vector<int> value = {6, 3, 5, 4, 6};
    int maxValue = knapsack(n, w, weight, value);
    cout << "最大价值为：" << maxValue << endl;
    return 0;
}

以上就是01背包问题回溯算法的C++代码实现。