0/1背包回溯法+分支限界法 c++

以下是0/1背包问题的回溯法和分支限界法的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) {
    if (i == n) {
        if (cv > maxv) maxv = cv;
        return;
    }
    dfs(i + 1, cw, cv);
    if (cw + w[i] <= W) {
        dfs(i + 1, cw + w[i], cv + 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];
    }
    dfs(0, 0, 0);
    cout << maxv << endl;
    return 0;
}

分支限界法：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

struct Node {
    int cw, cv, i;
    bool operator<(const Node& other) const {
        return cv < other.cv;
    }
};

void bfs() {
    priority_queue<Node> q;
    q.push({0, 0, 0});
    while (!q.empty()) {
        Node u = q.top(); q.pop();
        if (u.i == n) {
            if (u.cv > maxv) maxv = u.cv;
            continue;
        }
        if (u.cw + w[u.i] <= W) {
            q.push({u.cw + w[u.i], u.cv + v[u.i], u.i + 1});
        }
        q.push({u.cw, u.cv, u.i + 1});
    }
}

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

这里的回溯法和分支限界法都是使用了搜索的思想，回溯法是通过递归的方式枚举所有可能的情况，而分支限界法则是通过优先队列的方式，每次取出当前最优的节点进行拓展。