c++01背包问题回溯法

C++实现01背包问题的回溯法可以参考以下代码：

#include <iostream>
using namespace std;

const int MAXN = 100; //最大物品数量
int w[MAXN]; //物品重量
int v[MAXN]; //物品价值
int c; //背包容量
int n; //物品数量
int maxValue = 0; //最大价值
bool visited[MAXN]; //是否访问过

void Backtrack(int i, int cw, int cv) //i为当前物品编号，cw为当前重量，cv为当前价值
{
    if (i == n) //终止条件，已经选完所有物品
    {
        if (cv > maxValue) //更新最大价值
            maxValue = cv;
        return;
    }
    if (cw + w[i] <= c) //选择当前物品
    {
        visited[i] = true; //标记已访问
        Backtrack(i + 1, cw + w[i], cv + v[i]);
        visited[i] = false; //回溯，取消标记
    }
    Backtrack(i + 1, cw, cv); //不选择当前物品
}

int main()
{
    cin >> n >> c;
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
        visited[i] = false;
    }
    Backtrack(0, 0, 0);
    cout << maxValue << endl;
    return 0;
}

在这个回溯算法中，我们从第一个物品开始逐个考虑是否选择它。对于每个物品，我们有两种选择：选或不选。如果选择当前物品，我们需要将当前物品的重量和价值加到背包中，并且递归处理下一个物品。如果不选择当前物品，则直接递归处理下一个物品。对于每个物品，我们都要考虑选择和不选择两种情况，因此总的时间复杂度为指数级别。

这个算法的优点是实现简单，缺点是时间复杂度较高，只能处理较小的问题规模。如果要处理更大的问题，可以使用动态规划算法来解决。