分支限界法解决01背包

分支限界法是一种求解最优化问题的常见算法，可以用来解决01背包问题。具体步骤如下：

1. 将物品按照单位重量的价值从大到小排序。
2. 初始化一个优先队列，将初始节点（物品0装与不装）加入队列中。
3. 从队列中取出一个节点，如果该节点已经扩展完毕，则将其丢弃；否则，根据该节点的状态分别生成两个子节点，即将下一个物品装入背包和不装入背包两种情况。
4. 对于每个子节点，计算其上界（即当前状态下的最优解），如果上界比当前最优解更优，将其加入优先队列中。
5. 重复步骤3-4，直到队列为空。

具体实现时，可以使用一个结构体来表示每个节点的状态，包括当前已经装入背包的物品重量、价值、剩余可选物品等信息。同时，需要维护一个全局变量来记录当前最优解。

以下是一个简单的C++代码实现：

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

using namespace std;

struct Node {
    int weight, value, bound, level;
    bool operator<(const Node& other) const {
        return bound < other.bound;
    }
};

int n, capacity, ans;
int w[100], v[100];

int get_bound(int weight, int value, int level) {
    int bound = value;
    int rest = capacity - weight;
    for (int i = level; i < n; i++) {
        if (rest >= w[i]) {
            bound += v[i];
            rest -= w[i];
        } else {
            bound += (rest * v[i]) / w[i];
            break;
        }
    }
    return bound;
}

void branch_and_bound() {
    priority_queue<Node> q;
    Node u, v;
    u.level = u.weight = u.value = 0;
    u.bound = get_bound(0, 0, 0);
    q.push(u);
    while (!q.empty()) {
        u = q.top();
        q.pop();
        if (u.bound > ans) {
            v.level = u.level + 1;
            v.weight = u.weight + w[v.level - 1];
            v.value = u.value + v[v.level - 1];
            if (v.weight <= capacity && v.value > ans) {
                ans = v.value;
            }
            v.bound = get_bound(v.weight, v.value, v.level);
            if (v.bound > ans) {
                q.push(v);
            }
            v.weight = u.weight;
            v.value = u.value;
            v.bound = get_bound(v.weight, v.value, v.level);
            if (v.bound > ans) {
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> capacity;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    branch_and_bound();
    cout << ans << endl;
    return 0;
}

其中，get_bound函数用来计算节点的上界，主函数branch_and_bound则是按照上述步骤实现分支限界法求解01背包问题。