c++01背包问题回溯法

01背包问题是一个经典的动态规划问题，但是也可以用回溯法来解决。

具体思路是：从第一个物品开始，依次考虑是否将其放入背包中，如果放入，则将背包容量减少相应的重量，继续考虑下一个物品；如果不放入，则直接考虑下一个物品。当考虑完所有物品时，记录当前背包中的价值，与已知的最大价值进行比较，更新最大价值。

下面是C++代码实现：

#include <iostream>
using namespace std;

int N, W;
int w[100], v[100];
int maxValue = 0;

void backtrack(int i, int weight, int value) {
    if (i == N) {
        if (value > maxValue) {
            maxValue = value;
        }
        return;
    }
    if (weight + w[i] <= W) {
        backtrack(i+1, weight+w[i], value+v[i]); // 放入第i个物品
    }
    backtrack(i+1, weight, value); // 不放第i个物品
}

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    backtrack(0, 0, 0);
    cout << maxValue << endl;
    return 0;
}

其中，backtrack函数的参数含义分别为：当前考虑到的物品编号i，当前背包中已经装的物品重量weight，当前背包中已经装的物品价值value。