01背包问题分支限界法c++优先队列代码

01背包问题是一个经典的动态规划问题，当我们需要在给定的一组物品中选择一些放入容量有限的背包，使得总价值最大时，可以使用分支限界法求解。其中，优先队列用于存储待探索的状态，通常我们会使用最小堆来实现。

以下是一个简单的C++代码示例，使用了`std::priority_queue`（默认最小堆）来处理优先级：

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

// 定义物品结构
struct Item {
    int weight;
    int value;
};

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second / a.first > b.second / b.first; // 按价值密度排序
}

int knapsackBranchAndBound(vector<Item>& items, int capacity, vector<bool>& taken) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> pq(compare);
    pq.push({0, 0}); // 初始化队列，状态为0重量0，价值0

    while (!pq.empty()) {
        int currWeight = -pq.top().first;
        int currValue = pq.top().second;
        pq.pop();

        if (currWeight + items[taken.size()].weight <= capacity && 
            currValue + items[taken.size()].value > pq.top().second) {
            // 如果当前状态下背包未满，并且加入新物品的价值更大，更新背包状态
            taken.push_back(1);
            pq.push({-currWeight - items[taken.size()].weight, currValue + items[taken.size()].value});
        } else if (currWeight + items[taken.size()].weight <= capacity) {
            // 否则仅更新背包状态，不加入新物品
            taken.push_back(0);
            pq.push({-currWeight, currValue});
        } else {
            // 超出背包容量，无需再考虑该路径
        }
    }

    return currValue;
}

int main() {
    vector<Item> items = {{60, 100}, {100, 200}, {120, 300}};
    int capacity = 500;
    vector<bool> taken(items.size());
    cout << "Max value in the knapsack: " << knapsackBranchAndBound(items, capacity, taken) << endl;
    return 0;
}

在这个例子中，我们首先创建了一个优先队列`pq`，并初始化为空。然后，我们在循环中不断从队列中取出状态，判断是否符合条件（背包未满且加入新物品更有利），如果满足就更新背包状态并将其推入队列。当队列为空时，说明所有可能的情况都已检查过，返回当前的最大价值。