c++写出分支限界法0-1背包问题

好的，以下是C++代码实现分支限界法解决0-1背包问题：

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

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

struct cmp {
    bool operator() (const Node& a, const Node& b) {
        return a.bound < b.bound;//按照价值上界从小到大排序
    }
};

priority_queue<Node, vector<Node>, cmp> q;//使用优先队列实现分支限界法

float bound(Node u, int n, int c, int* w, int* p) {//计算价值上界
    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];//加上当前物品的重量
        bound += p[j];//加上当前物品的价值
        j++;//继续判断下一个物品
    }
    if(j < n) bound += (c - totweight) * (p[j] * 1.0 / w[j]);//如果还有物品需要判断，计算价值上界
    return bound;
}

int knapsack(int n, int c, int* w, int* p) {
    Node u, v;//u为扩展节点，v为左儿子节点
    int maxprofit = 0;//最大价值
    v.level = -1;//初始化为根节点
    v.profit = 0;
    v.weight = 0;
    v.bound = bound(v, n, c, w, p);//计算根节点的价值上界
    q.push(v);//将根节点加入队列
    while(!q.empty()) {
        v = q.top();//取出价值上界最小的节点
        q.pop();
        if(v.bound > maxprofit) {//如果可能存在更优解
            u.level = v.level + 1;//扩展节点的层数为父节点层数+1
            u.weight = v.weight + w[u.level];//扩展节点的重量为父节点重量加上当前物品的重量
            u.profit = v.profit + p[u.level];//扩展节点的价值为父节点价值加上当前物品的价值
            if(u.weight <= c && u.profit > maxprofit) maxprofit = u.profit;//更新最大价值
            u.bound = bound(u, n, c, w, p);//计算价值上界
            if(u.bound > maxprofit) q.push(u);//如果可能存在更优解，则将扩展节点加入队列
            u.weight = v.weight;//不选择当前物品
            u.profit = v.profit;
            u.bound = bound(u, n, c, w, p);//计算价值上界
            if(u.bound > maxprofit) q.push(u);//如果可能存在更优解，则将不选择当前物品的节点加入队列
        }
    }
    return maxprofit;
}

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

以上代码实现了分支限界法解决0-1背包问题，可以根据实际情况进行调整。