用c++实现0-1背包问题的回溯算法和分支限界算法

回溯算法实现0-1背包问题：

#include <iostream>
#include <algorithm>
using namespace std;

int n, c;
int w[100], v[100];
int ans;

void dfs(int idx, int cw, int cv) {
    if (idx == n) {
        if (cw <= c) ans = max(ans, cv);
        return;
    }
    dfs(idx + 1, cw, cv); // 不选第idx个物品
    if (cw + w[idx] <= c) dfs(idx + 1, cw + w[idx], cv + v[idx]); // 选第idx个物品
}

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

分支限界算法实现0-1背包问题：

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    int idx, cw, cv; // 物品编号，当前重量，当前价值
    double ub; // 上界
    bool operator < (const Node& other) const {
        return ub < other.ub;
    }
};

int n, c;
int w[100], v[100];
int ans;

double calcUb(int idx, int cw, int cv) {
    double ub = cv;
    int leftW = c - cw;
    while (idx < n && leftW >= w[idx]) {
        ub += v[idx];
        leftW -= w[idx];
        idx++;
    }
    if (idx < n) ub += (double)v[idx] / w[idx] * leftW;
    return ub;
}

void branchBound() {
    priority_queue<Node> pq;
    pq.push({0, 0, 0, calcUb(0, 0, 0)});
    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();
        if (node.idx == n) {
            ans = max(ans, node.cv);
            continue;
        }
        if (node.ub <= ans) continue; // 如果当前上界小于等于已知最优解，则不再扩展
        pq.push({node.idx + 1, node.cw, node.cv, calcUb(node.idx + 1, node.cw, node.cv)});
        if (node.cw + w[node.idx] <= c) {
            pq.push({node.idx + 1, node.cw + w[node.idx], node.cv + v[node.idx], calcUb(node.idx + 1, node.cw + w[node.idx], node.cv + v[node.idx])});
        }
    }
}

int main() {
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    branchBound();
    cout << ans << endl;
    return 0;
}