回溯法求解0-1背包c++

下面是使用回溯法求解0-1背包问题的C++代码：

#include <iostream>
#include <vector>

using namespace std;

int max_profit = 0; // 最大利润
vector<int> best_choice; // 最优解

// n: 物品数量
// w: 物品重量数组
// p: 物品价值数组
// c: 背包容量
// cur_weight: 当前选中的物品总重量
// cur_profit: 当前选中的物品总利润
// k: 当前搜索到的物品编号
void backtrack(int n, int w[], int p[], int c, int cur_weight, int cur_profit, int k)
{
    if (k == n) // 所有物品都已考虑过
    {
        if (cur_profit > max_profit) // 更新最大利润和最优解
        {
            max_profit = cur_profit;
            best_choice.clear();
            for (int i = 0; i < n; i++)
            {
                if (w[i] > 0) best_choice.push_back(i);
            }
        }
        return;
    }
    if (cur_weight + w[k] <= c) // 如果当前物品可以选
    {
        cur_weight += w[k];
        cur_profit += p[k];
        backtrack(n, w, p, c, cur_weight, cur_profit, k + 1); // 选中当前物品
        cur_weight -= w[k];
        cur_profit -= p[k];
    }
    backtrack(n, w, p, c, cur_weight, cur_profit, k + 1); // 不选当前物品
}

int main()
{
    int n = 5, c = 10; // 物品数量和背包容量
    int w[] = {2, 2, 6, 5, 4}; // 物品重量数组
    int p[] = {6, 3, 5, 4, 6}; // 物品价值数组
    backtrack(n, w, p, c, 0, 0, 0); // 开始搜索
    cout << "Max profit: " << max_profit << endl;
    cout << "Best choice: ";
    for (int i = 0; i < best_choice.size(); i++)
    {
        cout << best_choice[i] << " ";
    }
    cout << endl;
    return 0;
}

在上面的代码中，我们使用了一个全局变量`max_profit`来保存最大利润，使用一个`vector`类型的变量`best_choice`来保存最优解中选中的物品编号。在`backtrack`函数中，我们依次考虑每个物品是否选中，并递归搜索下一个物品，直到所有物品都被考虑过。在搜索过程中，如果当前选中的物品重量不超过背包容量，则将该物品选中，并继续搜索下一个物品；否则，不选中该物品。最后，在搜索结束后，输出最大利润和最优解。