01背包用带限界的回溯法写

以下是带限界的回溯法的C++代码：

#include <iostream>
#include <vector>

using namespace std;

int n, W;
vector<int> w, v;
int maxv = 0;

void dfs(int i, int cw, int cv, int ub) {
    if (i == n) {
        if (cv > maxv) maxv = cv;
        return;
    }
    if (cw + w[i] <= W) {
        dfs(i + 1, cw + w[i], cv + v[i], ub);
    }
    if (cv + ub > maxv) {
        dfs(i + 1, cw, cv, ub - v[i]);
    }
}

int main() {
    cin >> n >> W;
    w.resize(n);
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    int ub = 0;
    for (int i = 0; i < n; i++) {
        ub += v[i];
    }
    dfs(0, 0, 0, ub);
    cout << maxv << endl;
    return 0;
}

这里的带限界的回溯法与普通的回溯法的区别在于，加入了一个上界（ub）的限制，用来判断是否需要继续搜索。在每次递归时，如果当前节点的价值加上剩余物品的最大价值仍然小于当前最大价值，则可以剪枝，直接返回。