分支限界法求解0/1背包问题c++代码

以下是使用分支限界法求解0/1背包问题的C++代码：

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

using namespace std;

struct Node {
    int level;
    int profit;
    int weight;
    double bound;
};

bool operator<(const Node& a, const Node& b) {
    return a.bound < b.bound;
}

double bound(Node u, int n, int W, vector<pair<int, int>>& items) {
    if (u.weight >= W) {
        return 0;
    }
    double profitBound = u.profit;
    int j = u.level + 1;
    int totalWeight = u.weight;
    while ((j < n) && (totalWeight + items[j].second <= W)) {
        totalWeight += items[j].second;
        profitBound += items[j].first;
        j++;
    }
    if (j < n) {
        profitBound += (W - totalWeight) * (double)items[j].first / items[j].second;
    }
    return profitBound;
}

int knapsack(int n, int W, vector<pair<int, int>>& items) {
    priority_queue<Node> pq;
    Node u, v;
    pq.push({-1, 0, 0, 0});
    int maxProfit = 0;
    while (!pq.empty()) {
        u = pq.top();
        pq.pop();
        if (u.level == n - 1) {
            continue;
        }
        v.level = u.level + 1;
        v.weight = u.weight + items[v.level].second;
        v.profit = u.profit + items[v.level].first;
        if (v.weight <= W && v.profit > maxProfit) {
            maxProfit = v.profit;
        }
        v.bound = bound(v, n, W, items);
        if (v.bound > maxProfit) {
            pq.push(v);
        }
        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = bound(v, n, W, items);
        if (v.bound > maxProfit) {
            pq.push(v);
        }
    }
    return maxProfit;
}

int main() {
    int n = 4;
    int W = 10;
    vector<pair<int, int>> items = {{40, 2}, {30, 5}, {50, 10}, {10, 5}};
    int result = knapsack(n, W, items);
    cout << "Maximum profit: " << result << endl;
    return 0;
}

在上面的代码中，我们首先定义了一个结构体`Node`，其中包含了四个成员变量`level`、`profit`、`weight`和`bound`，分别表示当前节点在决策树中的层数、当前的利润、当前的重量和当前节点的上界。另外，我们还定义了一个小于号运算符，用于将结构体按照上界从小到大排序。

然后，我们定义了一个`bound`函数，用于计算当前节点的上界。在计算上界的过程中，我们首先判断当前节点的重量是否超出了背包的容量，如果是的话，直接返回0。否则，我们将当前节点的利润作为上界的初始值，然后从当前节点的下一个节点开始，依次加入物品，直到背包装满或者物品加完为止。如果还有剩余的空间，我们按照单位重量的价值将剩余的物品加入背包，然后返回计算出的上界。

接下来，我们定义了一个`knapsack`函数，用于求解0/1背包问题。在函数中，我们首先定义了一个优先队列`pq`，用于保存当前还未扩展的节点。然后，我们将根节点加入队列中。之后，我们不断从队列中取出上界最小的节点并进行扩展，如果当前节点已经是叶子节点，则直接跳过。否则，我们分别计算出将当前节点的下一个节点加入背包和不加入背包的两种情况下的上界，并将对应的节点加入队列中。如果当前节点的上界已经小于已知的最大利润，则直接跳过。如果队列为空时，我们已经搜索完了整个决策树，此时的最大利润即为问题的解。

最后，我们在`main`函数中调用`knapsack`函数求解0/1背包问题，并输出结果。