0/1背包问题回溯法的C++代码

以下是一个使用回溯法解决0/1背包问题的简单示例代码：

#include <iostream>
#include <vector>

using namespace std;

int maxWeight = 0; // 最大重量
vector<int> curItems; // 当前选择的物品
vector<int> bestItems; // 最优选择的物品

void backtrack(int currentIndex, int currentWeight, int capacity, vector<int>& weights) {
    if (currentIndex >= weights.size() || currentWeight == capacity) {
        if (currentWeight > maxWeight) {
            maxWeight = currentWeight;
            bestItems = curItems;
        }
        return;
    }

    if (currentWeight + weights[currentIndex] <= capacity) {
        curItems.push_back(weights[currentIndex]);
        backtrack(currentIndex + 1, currentWeight + weights[currentIndex], capacity, weights);
        curItems.pop_back();
    }

    backtrack(currentIndex + 1, currentWeight, capacity, weights);
}

int main() {
    vector<int> weights = {2, 3, 4, 5}; // 物品重量
    int capacity = 7; // 背包容量

    backtrack(0, 0, capacity, weights);

    cout << "最大重量: " << maxWeight << endl;
    cout << "最优选择的物品: ";
    for (int item : bestItems) {
        cout << item << " ";
    }
    cout << endl;

    return 0;
}

这段代码使用递归回溯的方法，通过枚举每个物品的选择情况来求解0/1背包问题。在回溯过程中，维护当前选择的物品和当前总重量，并根据约束条件进行剪枝。最后输出最大重量和最优选择的物品。注意，这只是一个简单的示例代码，实际问题中可能需要考虑更多因素和优化策略。