用分支限界法解决0/1背包问题的C++代码

好的，这里给你一个用分支限界法解决0/1背包问题的C++代码，希望能够帮到你。

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

struct Node {
    int level; // 当前节点的深度
    int weight; // 当前节点的背包重量
    int value; // 当前节点的背包价值
    double bound; // 当前节点的价值上界
    vector<int> flag; // 当前节点的物品选择情况
};

bool cmp(const pair<double, int>& a, const pair<double, int>& b) { // 按单位重量价值从大到小排序
    return a.first > b.first;
}

double bound(Node node, int n, int c, vector<int>& w, vector<int>& v) { // 计算价值上界
    if (node.weight >= c) {
        return 0;
    } else {
        double bound = node.value;
        int j = node.level + 1;
        int totweight = node.weight;
        while (j < n && totweight + w[j] <= c) {
            totweight += w[j];
            bound += v[j];
            j++;
        }
        if (j < n) {
            bound += (c - totweight) * (double)v[j] / w[j];
        }
        return bound;
    }
}

int knapsack_bfs(int n, int c, vector<int>& w, vector<int>& v) { // 分支限界法解决0/1背包问题
    priority_queue<pair<double, Node>> Q; // 优先队列，按价值上界从大到小排序
    Node root = {-1, 0, 0, 0.0, {}};
    Q.push(make_pair(0, root));
    int maxvalue = 0;
    while (!Q.empty()) {
        Node node = Q.top().second;
        Q.pop();
        if (node.level == n - 1) {
            continue;
        }
        vector<int> flag1 = node.flag;
        flag1.push_back(0);
        Node child1 = {node.level+1, node.weight, node.value, 0.0, flag1};
        child1.bound = bound(child1, n, c, w, v);
        if (child1.bound > maxvalue) {
            Q.push(make_pair(child1.bound, child1));
            maxvalue = max(maxvalue, child1.value);
        }
        vector<int> flag2 = node.flag;
        flag2.push_back(1);
        Node child2 = {node.level+1, node.weight+w[node.level+1], node.value+v[node.level+1], 0.0, flag2};
        child2.bound = bound(child2, n, c, w, v);
        if (child2.bound > maxvalue) {
            Q.push(make_pair(child2.bound, child2));
            maxvalue = max(maxvalue, child2.value);
        }
    }
    return maxvalue;
}

int main() {
    int n = 4;
    int c = 8;
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    vector<pair<double, int>> vw(n);
    for (int i = 0; i < n; i++) {
        vw[i] = make_pair((double)v[i] / w[i], i);
    }
    sort(vw.begin(), vw.end(), cmp); // 按单位重量价值从大到小排序
    vector<int> new_w(n);
    vector<int> new_v(n);
    for (int i = 0; i < n; i++) {
        new_w[i] = w[vw[i].second];
        new_v[i] = v[vw[i].second];
    }
    cout << knapsack_bfs(n, c, new_w, new_v) << endl;
    return 0;
}

代码中的 `Node` 结构体表示搜索树的一个节点，其中 `level` 表示当前节点的深度，`weight` 表示当前节点的背包重量，`value` 表示当前节点的背包价值，`bound` 表示当前节点的价值上界，`flag` 表示当前节点的物品选择情况。`cmp` 函数用于按单位重量价值从大到小排序，`bound` 函数用于计算当前节点的价值上界，`knapsack_bfs` 函数是分支限界法的具体实现，用于解决0/1背包问题。