回溯法0-1背包问题递归c++

以下是回溯法求解0-1背包问题的递归实现，C++代码如下：

#include <iostream>
using namespace std;

const int N = 5;  // 物品数量
const int V = 10; // 背包容量

int w[N] = {2, 2, 6, 5, 4}; // 物品重量
int v[N] = {6, 3, 5, 4, 6}; // 物品价值

int maxV = 0; // 最大价值

void dfs(int i, int cw, int cv)
{
    if (i == N) // 搜索到最后一个物品
    {
        if (cv > maxV)
            maxV = cv;
        return;
    }

    dfs(i + 1, cw, cv); // 不选第i个物品

    if (cw + w[i] <= V)
        dfs(i + 1, cw + w[i], cv + v[i]); // 选第i个物品
}

int main()
{
    dfs(0, 0, 0);
    cout << maxV << endl;

    return 0;
}

其中，dfs函数用于搜索所有可能的方案，i表示当前搜索到的物品编号，cw表示当前已经装入背包的物品重量，cv表示当前的总价值。如果搜索到最后一个物品，就更新最大价值maxV。在搜索过程中，每次可以选择不装当前物品或者装入当前物品。如果选择装入当前物品，则需要判断加入当前物品后是否超出背包容量。