用c++实现优先队列分支定界法解决 01 背包问题

以下是用C++实现优先队列分支定界法解决01背包问题的代码：

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

struct Node {
    int level; // 当前节点所在层
    int profit; // 当前节点产生的总价值
    int weight; // 当前节点产生的总重量
    float bound; // 当前节点的价值上界

    bool operator<(const Node& other) const {
        return bound < other.bound; // 按价值上界从大到小排序
    }
};

float bound(Node u, int n, int* w, int* p, int c) {
    if (u.weight >= c) {
        return 0; // 已经超重，价值上界为0
    }
    float bound = u.profit;
    int j = u.level + 1;
    int totweight = u.weight;
    while ((j < n) && (totweight + w[j] <= c)) {
        totweight += w[j]; // 选第j件物品
        bound += p[j];
        j++;
    }
    if (j < n) {
        bound += (c - totweight) * p[j] / w[j]; // 加上部分物品的价值
    }
    return bound;
}

int knapsack(int n, int* w, int* p, int c) {
    priority_queue<Node> Q;
    Node u, v;
    u.level = -1;
    u.profit = 0;
    u.weight = 0;
    u.bound = bound(u, n, w, p, c);
    int maxprofit = 0;
    Q.push(u);
    while (!Q.empty()) {
        u = Q.top();
        Q.pop();
        if (u.bound > maxprofit) {
            v.level = u.level + 1;
            v.weight = u.weight + w[v.level];
            v.profit = u.profit + p[v.level];
            if (v.weight <= c && v.profit > maxprofit) {
                maxprofit = v.profit; // 更新最大价值
            }
            v.bound = bound(v, n, w, p, c);
            if (v.bound > maxprofit) {
                Q.push(v); // 左儿子节点入队
            }
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = bound(v, n, w, p, c);
            if (v.bound > maxprofit) {
                Q.push(v); // 右儿子节点入队
            }
        }
    }
    return maxprofit;
}

int main() {
    int n = 5; // 物品数量
    int w[] = {2, 2, 6, 5, 4}; // 物品重量数组
    int p[] = {6, 3, 5, 4, 6}; // 物品价值数组
    int c = 10; // 背包容量
    cout << "最大价值为：" << knapsack(n, w, p, c) << endl;
    return 0;
}

代码中，Node结构体表示搜索树的一个节点，其中level表示当前节点所在层，profit表示当前节点产生的总价值，weight表示当前节点产生的总重量，bound表示当前节点的价值上界。由于需要按照价值上界从大到小排序，因此使用了STL中的priority_queue作为优先队列。

bound函数计算一个节点的价值上界，如果当前节点的重量已经超过背包容量，则价值上界为0；否则，将当前节点的价值加上剩余物品的部分价值，直到超重或者所有物品都选完。

knapsack函数是实现01背包问题的主函数，首先初始化根节点u，然后将其入队。接下来，每次取出优先队列的队首元素u，如果当前节点的价值上界大于当前最大价值，则生成它的左儿子节点v和右儿子节点v'，并计算它们的价值上界。如果左儿子节点v的重量小于等于背包容量且产生的价值大于当前最大价值，则更新最大价值。将v和v'按照价值上界从大到小的顺序入队。重复这个过程直到队列为空。