具体解题思路和代码来自

0-1背包问题-分支限界法(优先队列分支限界法)_小莫の咕哒君-CSDN博客_背包问题分支限界法

我这里只是在init函数这里修改了一些部分，只需要修改关键部分也可以运行

代码部分如下：

#include <stdlib.h>
#include <iostream>
#include<algorithm>
#include <queue>
using namespace std;
class Object
{
public:
    int id;     //物品id
    int weight; //重量
    int value;  //价值
    float d;    
};
class MaxHeapQNode
{
public:
    MaxHeapQNode* parent;
    int lchild;
    int upprofit;
    int profit;
    int weight;
    int lev;
};
struct cmp
{
    bool operator()(MaxHeapQNode*& a, MaxHeapQNode*& b) const
    {
        return a->upprofit < b->upprofit;
    }
};
bool compare(const Object& a, const Object& b)
{
    return a.d >= b.d;
}
int n;
int c;
int cw;
int cp;
int bestp;
Object obj[100];
int bestx[100];
void init()
{
    
    /*int weights[6] = { 0 , 12 , 7 , 11 , 8 , 9 };
    int values[6] = { 0 , 24, 13 ,23 , 15, 16 };
    n = 5;
    c = 26;*/
    int weights[11] = { 0,23,31,29,44,53,38,63,85,89,82 };     
    int values[11] = { 0,92,57,49,68,60,43,67,84,87,72 };  
    n = 10;
    c = 165;
    for (int i = 1; i <= n; ++i)
    {
        obj[i].value = values[i]; 
        obj[i].weight = weights[i];
        obj[i].id = i;
        obj[i].d = 1.0 * obj[i].value / obj[i].weight;
    }

    sort(obj + 1, obj + n + 1, compare);
    //    for(int i = 1; i <= n; ++i)
    //        cout << obj[i].d << " ";
    //    cout << endl << "InPut Complete" << endl;
}
int bound(int i)
{
    int tmp_cleft = c - cw;
    int tmp_cp = cp;
    while (tmp_cleft >= obj[i].weight && i <= n)
    {
        tmp_cleft -= obj[i].weight;
        tmp_cp += obj[i].value;
        i++;
    }
    if (i <= n)
    {
        tmp_cp += tmp_cleft * obj[i].d;
    }
    return tmp_cp;
}
void addAliveNode(priority_queue<MaxHeapQNode*, vector<MaxHeapQNode*>, cmp>& q, MaxHeapQNode* E, int up, int wt, int curp, int i, int ch)
{
    MaxHeapQNode* p = new MaxHeapQNode;
    p->parent = E;
    p->lchild = ch;
    p->weight = wt;
    p->upprofit = up;
    p->profit = curp;
    p->lev = i + 1;
    q.push(p);
    //    cout << "加入点的信息为 " << endl;
    //    cout << "p->lev = " << p->lev << " p->upprofit = " << p->upprofit << " p->weight =  " << p->weight << " p->profit =  " << p->profit << endl;
}
void maxKnapsack()
{
    priority_queue<MaxHeapQNode*, vector<MaxHeapQNode*>, cmp > q; // 大顶堆
    MaxHeapQNode* E = NULL;
    cw = cp = bestp = 0;
    int i = 1;
    int up = bound(1); //Bound(i)函数计算的是i还未处理时候的上限值
    while (i != n + 1)
    {
        int wt = cw + obj[i].weight;
        if (wt <= c)
        {
            if (bestp < cp + obj[i].value)
                bestp = cp + obj[i].value;
            addAliveNode(q, E, up, cw + obj[i].weight, cp + obj[i].value, i, 1);
        }
        up = bound(i + 1); //注意这里 up != up - obj[i].price而且 up >= up - obj[i].price
        if (up >= bestp) //注意这里必须是大于等于
        {
            addAliveNode(q, E, up, cw, cp, i, 0);
        }
        E = q.top();
        q.pop();
        cw = E->weight;
        cp = E->profit;
        up = E->upprofit;
        i = E->lev;
    }
    for (int j = n; j > 0; --j)
    {
        bestx[obj[E->lev - 1].id] = E->lchild;
        E = E->parent;
    }
}
void output()
{
    //printf("最优装入量为 %d\n", bestp);
    for (int i = 1; i <= n; ++i) {
        if (bestx[i] == 1) {
            cout << "1 ";
        }
        else {
            cout << "0 ";
        }
    }
        
}
int main()
{
    init();
    maxKnapsack();
    output();
    return 0;
}