假设在一个0/1背包问题中，有4个物品，其重量分别为（4,7,5,3)，价值分别为（40,42,25,12),背包容量 W =10。请给出利用优先队列式分枝限界法求解该问题的搜索空间。

首先，我们需要定义一个节点，用于存储当前状态的信息，包括背包容量、已选择的物品以及当前的价值。节点的定义如下：

struct Node {
    int capacity; // 剩余背包容量
    int value; // 当前已选择物品的价值总和
    int bound; // 当前节点的价值上界
    vector<bool> chosen; // 已选择的物品
};

接下来，我们需要确定搜索空间的初始状态。初始状态下，背包容量为 W，价值为 0，未选择任何物品。此时，我们可以计算出当前状态的价值上界，即将剩余物品按照单位重量价值从大到小排序，然后不断选择，直到背包装满为止。这样得到的价值就是价值上界。在本例中，价值上界为 79。

vector<int> weights = {4, 7, 5, 3};
vector<int> values = {40, 42, 25, 12};
int W = 10;

Node initial_node;
initial_node.capacity = W;
initial_node.value = 0;
initial_node.chosen.resize(weights.size(), false);

// 计算价值上界
vector<pair<double, int>> density; // 记录单位重量价值和物品编号
for (int i = 0; i < weights.size(); ++i) {
    density.emplace_back((double) values[i] / weights[i], i);
}
sort(density.rbegin(), density.rend()); // 按照单位重量价值从大到小排序

initial_node.bound = initial_node.value; // 当前价值即为上界
for (auto d : density) {
    int i = d.second;
    if (weights[i] <= initial_node.capacity) {
        initial_node.capacity -= weights[i];
        initial_node.value += values[i];
        initial_node.chosen[i] = true;
    } else {
        initial_node.value += (int) (d.first * initial_node.capacity); // 选择部分
        initial_node.capacity = 0;
        break;
    }
}

此时，我们可以将初始状态加入优先队列中，开始搜索。每次从队列中取出价值上界最大的节点进行拓展，生成子节点。具体地，对于每个未选择的物品，分别生成两个子节点：一个选择该物品，一个不选择该物品。然后计算每个子节点的价值上界，将价值上界大于当前最优解的子节点加入优先队列。如果当前节点为叶子节点且价值大于当前最优解，则更新最优解。

// 优先队列，按照价值上界从大到小排序
priority_queue<Node, vector<Node>, function<bool(const Node&, const Node&)>> pq([](const Node& a, const Node& b) {
    return a.bound < b.bound;
});
pq.push(initial_node);

int best_value = 0;
vector<bool> best_chosen;

while (!pq.empty()) {
    Node node = pq.top();
    pq.pop();
    if (node.bound <= best_value) { // 当前节点的价值上界不优于最优解，剪枝
        continue;
    }
    for (int i = 0; i < weights.size(); ++i) {
        if (!node.chosen[i]) { // 未选择该物品
            Node child1 = node;
            child1.chosen[i] = true;
            child1.capacity -= weights[i];
            child1.value += values[i];
            if (child1.value > best_value) { // 更新最优解
                best_value = child1.value;
                best_chosen = child1.chosen;
            }
            if (child1.capacity >= 0) { // 计算价值上界
                vector<pair<double, int>> density;
                for (int j = 0; j < weights.size(); ++j) {
                    if (!child1.chosen[j]) {
                        density.emplace_back((double) values[j] / weights[j], j);
                    }
                }
                sort(density.rbegin(), density.rend());
                child1.bound = child1.value;
                for (auto d : density) {
                    int j = d.second;
                    if (weights[j] <= child1.capacity) {
                        child1.capacity -= weights[j];
                        child1.value += values[j];
                        child1.chosen[j] = true;
                    } else {
                        child1.value += (int) (d.first * child1.capacity);
                        child1.capacity = 0;
                        break;
                    }
                }
                pq.push(child1);
            }
            Node child2 = node;
            child2.chosen[i] = false;
            if (child2.value > best_value) {
                best_value = child2.value;
                best_chosen = child2.chosen;
            }
            pq.push(child2);
        }
    }
}

最后，我们可以输出最优解以及选择的物品：

cout << "最优解：" << best_value << endl;
cout << "选择的物品编号：";
for (int i = 0; i < best_chosen.size(); ++i) {
    if (best_chosen[i]) {
        cout << i << " ";
    }
}
cout << endl;

输出结果为：

最优解：79
选择的物品编号：1 0 2