優先隊列式分支限界法求解0-1背包問題

#include <iostream>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;
#define n 4
int w[n]= {3,5,2,1},v[n]= {9,10,7,4},x[n]= {0};
int W=7;
double cw=0,cp=0,bestp=0,UP=0;
class QNode
{
public:
    double cw; //目前背包中物品的重量
    double cp; //目前背包中物品的價值
    bool isLeft; //是否為左子樹
    int level; //結點所處的層
    double up;
    QNode *parentNode; //QNode父節點
    QNode()
    {
        cw=0;
        cp=0;
        isLeft=true;
        level=0;
        up=0;
    }
    QNode(double _cw,double _cp,bool _isLeft,int _level,double _up,QNode *_parentNode=NULL)
    {
        cw=_cw;
        cp=_cp;
        isLeft=_isLeft;
        level=_level;
        up=_up;
        parentNode=_parentNode;
    }
};
QNode *qNode=NULL,*retQNode=NULL;
struct Dvalue
{
    int id;
    double DV;
};
int f(const void *a,const void *b)//升序
{
    int t;
    if((*(Dvalue *)a).DV>(*(Dvalue *)b).DV)
    {
        t=-1;
    }
    else
        t=1;
    return t;
}
struct cmp
{
    bool operator()(QNode *&a,QNode *&b)
    {
        return a->up<b->up;
    }
};
priority_queue<QNode *,vector<QNode *>,cmp > q;
double bound(int i)
{
    Dvalue d[n-i];
    int c=0,k=0;
    double b=cp;
    double cleft=W-cw;
    for(int j=i; j<n; j++) //先對物品按照機關重量的價值非減排序
    {
        d[c].id=j;
        d[c].DV=v[j]/w[j];
        c++;
    }
    qsort(d,c,sizeof(d[0]),f);
    while(k<c&&w[d[k].id]<=cleft)
    {
        cleft-=w[d[k].id];
        b+=v[d[k].id];
        k++;
    }
    if(k<c)
    {
        b+=(v[d[k].id]/w[d[k].id])*cleft;
    }
    return b;
}
QNode *Q_BB_KNAPSACK_01()
{
    int i=0;
    while(true)
    {
        if(i==n) //到達葉子結點
        {
            retQNode=qNode;
            break;
        }
        if(cw+w[i]<=W)//左子結點。這裡也可以考慮限界條件
        {
            bestp=(cp+v[i]>bestp)?cp+v[i]:bestp;
            QNode *q2=new QNode(cw+w[i],cp+v[i],true,i+1,bound(i+1),qNode);
            UP=q2->up>UP?q2->up:UP;
//            cout<<W-q2->cw<<" "<<q2->cp<<endl;
            q.push(q2);
        }
        if(q.top()!=NULL&&bound(i+1)>bestp)//右子結點
        {
            QNode *q1=new QNode(cw,cp,false,i+1,bound(i+1),qNode);
//            cout<<W-q1->cw<<" "<<q1->cp<<endl;
            if(q1->up>UP)
            q.push(q1);
        }
        qNode=q.top();
        q.pop();
        cw=qNode->cw;
        cp=qNode->cp;
        i=qNode->level;
    }
    return retQNode;
}
int main()
{
    QNode *Q;
    Q=Q_BB_KNAPSACK_01();
    cout<<bestp<<endl;
    int c=n-1;
    while(Q!=NULL)
    {
        x[c--]=Q->isLeft;
        Q=Q->parentNode;
    }
    for(int i=0; i<n; i++)
    {
        cout<<x[i]<<" ";
    }
    return 0;
}