，C++分支限界法求解背包问题

1.beibao.h文件代码如下：

#ifndef BEIBAO_H
#define  BEIBAO_H

#include <math.h>


//子空间中节点类型
class BBnode{
public: 
        BBnode*  parent;   //父节点
        bool leftChild;   //左儿子节点标志
        BBnode(BBnode* par,bool ch){
                parent=par;
                leftChild=ch;
        }
        BBnode(){

        }
};

class HeapNode {
public:
        BBnode* liveNode; // 活结点
        double  upperProfit; //结点的价值上界
        double  profit; //结点所相应的价值
        double  weight; //结点所相应的重量
        int     level; // 活结点在子集树中所处的层次号

        //构造方法
         HeapNode(BBnode* node, double up, double pp , double ww,int lev){
                liveNode = node;
                upperProfit = up;
                profit    = pp;
                weight    = ww;
                level    = lev;
        }
         HeapNode(){

         }
         int compareTo(HeapNode o) {
                double xup =o.upperProfit;
                if(upperProfit < xup)
                        return -1;
                if(upperProfit == xup)
                        return 0;
                else
                        return 1;
        }
};

class Element  {
public:
        int id;
        double d;
        Element(){

        }
        Element(int idd,double dd){
                id=idd;
                d=dd;
        }
        int compareTo(Element x){
                double xd=x.d;
                if(d<xd)return -1;
                if(d==xd)return 0;
                return 1;
        }
         bool equals(Element x){
                return d==x.d;
        }
};

class MaxHeap{
public:
         HeapNode *nodes;
         int nextPlace;
         int maxNumber;
         MaxHeap(int n){
                maxNumber = pow((double)2,(double)n);
                nextPlace = 1;//下一个存放位置
                nodes = new HeapNode[maxNumber];
        }
         MaxHeap(){
         }
    void put(HeapNode node){
                nodes[nextPlace] = node;
                nextPlace++;
                heapSort(nodes);
        }
        HeapNode removeMax(){
                HeapNode tempNode = nodes[1];
                nextPlace--;
                nodes[1] = nodes[nextPlace];
                heapSort(nodes);
                return tempNode;
        }
         void heapAdjust(HeapNode *  nodes,int s,int m){
                HeapNode rc = nodes[s];
                for(int j=2*s;j<=m;j*=2){
                        if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)
                                ++j;
                        if(!(rc.upperProfit<nodes[j].upperProfit))
                                break;
                        nodes[s] = nodes[j];
                        s = j;
                }
                nodes[s] = rc;
        }
    void heapSort(HeapNode * nodes){
                for(int i=(nextPlace-1)/2;i>0;--i){
                        heapAdjust(nodes,i,nextPlace-1);
                }
        }
} ;


#endif

2.测试代码

#include <iostream>
using namespace std;



//子空间中节点类型
#include "beibao.h"


double c=30; 
const int n=3;
double *w;
double *p;
double cw;
double cp;
int    *bestX;
MaxHeap * heap;


//上界函数bound计算结点所相应价值的上界
 double bound(int i){
        double cleft=c-cw;
        double b=cp;
        while(i<=n&&w[i]<=cleft){
                cleft=cleft-w[i];
                b=b+p[i];
                i++;
        }
        //装填剩余容量装满背包
        if(i<=n)
                b=b+p[i]/w[i]*cleft;
        return b;
}
//addLiveNode将一个新的活结点插入到子集树和优先队列中
 void addLiveNode(double up,double pp,double ww,int lev,BBnode* par,bool ch){
        //将一个新的活结点插入到子集树和最大堆中
        BBnode *b=new BBnode(par,ch);
        HeapNode  node =HeapNode(b,up,pp,ww,lev);
        heap->put(node);
}
 double MaxKnapsack(){
        //优先队列式分支限界法，返回最大价值，bestx返回最优解
        BBnode * enode=new BBnode();
        int i=1;
        double bestp=0;//当前最优值
        double up=bound(1);//当前上界
        while(i!=n+1){//非叶子结点
                //检查当前扩展结点的左儿子子结点
                double wt=cw+w[i];
                if(wt<=c){
                        if(cp+p[i]>bestp)
                                bestp=cp+p[i];
                        addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);
                }
                up=bound(i+1);
                if(up>=bestp)
                        addLiveNode(up,cp,cw,i+1,enode,false);
                HeapNode node =heap->removeMax();
                enode=node.liveNode;
                cw=node.weight;
                cp=node.profit;
                up=node.upperProfit;
                i=node.level;
        }
        for(int j=n;j>0;j--){

                bestX[j]=(enode->leftChild)?1:0;
                enode=enode->parent;
        }
        return cp;
}


 double knapsack(double *pp,double *ww,double cc,int *xx){
        //返回最大值，bestX返回最优解
        c=cc;
        //n=sizeof(pp)/sizeof(double);
        //定义以单位重量价值排序的物品数组
        Element *q=new Element[n];
        double ws=0.0;
        double ps=0.0;
        for(int i=0;i<n;i++){
                q[i]=Element(i+1,pp[i+1]/ww[i+1]);
                ps=ps+pp[i+1];
                ws=ws+ww[i+1];
        }
        if(ws<=c){
                return  ps;
        }           
        p=new double[n+1];
        w=new double[n+1];
        for(int i=0;i<n;i++){
                p[i+1]=pp[q[i].id];
                w[i+1]=ww[q[i].id];
        }
        cw=0.0;
        cp=0.0;
        bestX = new int[n+1];
        heap = new MaxHeap(n);
        double bestp = MaxKnapsack();
        for(int j=0;j<n;j++)
                xx[q[j].id]=bestX[j+1];

        return  bestp;

}




void main(){
        
        w=new double[4];
        w[1]=16;w[2]=15;w[3]=15;
        p=new double[4];
        p[1]=45;p[2]=25;p[3]=25;
        int *x = new int[4];
        double m = knapsack(p,w,c,x);


        cout<<"*****分支限界法*****"<<endl;
        cout<<"*****物品个数：n="<<n<<endl;
        cout<<"*****背包容量：c="<<c<<endl;
        cout<<"*****物品重量数组：w= {"<<w[3]<<" "<<w[1]<<" "<<w[2]<<"}"<<endl;
        cout<<"*****物品价值数组：v= {"<<p[3]<<" "<<p[1]<<" "<<p[2]<<"}"<<endl;
        cout<<"*****最优值：="<<m<<endl;
        cout<<"*****选中的物品是:";
        for(int i=1;i<=3;i++)
                cout<<x[i]<<" ";
        cout<<endl;
}

3.测试结果：

*****分支限界法*****
*****物品个数：n=3
*****背包容量：c=30
*****物品重量数组：w= {15 16 15}
*****物品价值数组：v= {25 45 25}
*****最优值：=50
*****选中的物品是:0 1 1