0-1背包-分支限界-白红宇

算法描述：

　　活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。

　　子集树中以结点N为根的子树中任一结点的价值不超过N.profit。

　　可用一个最大堆来实现或节点优先队列。

　　N.weight 是结点N所相应的重量，N.profit是N所相应的价值，N.uprofit是结点N的价值上界，最大堆以这个值作为优先级。

class Object{    friend int Knapsack(int *,int *,int ,int ,int *);public:    int operator <= (Object a) const    {        return (d >= a.d);    }private:    int ID;    float d;};template 
      
        class Knap;class bbnode{    friend Knap
       
        ;    friend int Knapsack(int *,int *,int,int,int *);private:    bbnode * parent;    bool LChild;};template 
        
         class HeapNode{    friend Knap
         
          ;public:    operator Typep() const     {        return uprofit;    }private:    Typep uprofit,//结点价值上界        profit;    Typew weight;    int level;//活结点所相应的重量    bbnode * ptr;};

上界计算函数：

template 
      
       class Knap
       
        ::Bound(int i){    Typew cleft = c- cw;//剩余容量    Typep b = cp;//价值上界    //以物品单位重量价值递减序装填剩余容量    while(i<=n && w[i] <= cleft)    {        cleft -= w[i];        b += p[i];        i++;    }    //装填剩余容量装满背包    if(i<=n)        b += p[i]/w[i] * cleft;    return b;}

分支限界搜索函数：

template 
      
       Typep Knap
       
        ::MaxKnapsack(){    //优先队列式分支限界法，返回最大价值，bestx返回最优解    //定义最大堆的容量为1000    H = new MaxHeap< HeapNode
        
          >(1000);    //为bestx分配存储空间    bestx = new int [n+1];    //初始化    int i=1;    E= 0;    cw = cp = 0;    Typep bestp = 0;    Typep up = Bound(1);    //搜索子集空间树    while(i!=n+1)//非叶节点    {        //检查当前扩展结点的左儿子结点        Typew wt = cw + w[i];        if(wt <= c)        {            if(cp+p[i] > bestp)                bestp = cp+p[i];            AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);        }        up = Bound(i+1);        //检查扩展结点的右儿子结点        if(up >= bestp)//右子树 可能含有最优解            AddLiveNode(up,cp,cw,false,i+1);                //取得下一扩展点        HeapNode
         
           N;        H->DeleteMax(N);        E = N.ptr;        cw = N.weight;        cp = N.profit;        up = N.uprofit;        i = N.level;    }    //构造当前最优解    for(int j=n;j>0;j--)    {        bestx[j] = E->LChild;        E = E->parent;    }    return cp;}

主要程序代码：

测试中.....（暂时不好使）

#include 
      
       #include 
       
        class Object{    friend int Knapsack(int *,int *,int ,int ,int *);public:    int operator <= (Object a) const    {        return (d >= a.d);    }private:    int ID;    float d;};template 
        
          class Knap;class bbnode{    friend Knap
         
          ;    friend int Knapsack(int *,int *,int,int,int *);private:    bbnode * parent;    bool LChild;};template 
          
           class HeapNode{    friend Knap
           
            ;public: operator Typep() const { return uprofit; }private: Typep uprofit,//结点价值上界 profit; Typew weight; int level;//活结点所相应的重量 bbnode * ptr;};template 
            
             class Knap{ friend Typep Knapsack(Typep *,Typew *,Typew ,int ,int *);public: Typep MaxKnapsack();private: MaxHeap
             
              
                > * H; Typep Bound(int i); void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int level); bbnode * E; Typew c; int n; Typew * w; Typep *p; Typew cw; Typep cp; int *bestx;};template 
               
                class Knap
                
                 ::Bound(int i){ Typew cleft = c- cw;//剩余容量 Typep b = cp;//价值上界 //以物品单位重量价值递减序装填剩余容量 while(i<=n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } //装填剩余容量装满背包 if(i<=n) b += p[i]/w[i] * cleft; return b;}template 
                 
                  void Knap
                  
                   ::AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev){ //将一个新的活结点插入到子集树 和 最大堆 H中 bbnode *b = new bbnode; b->parent = E; b->LChild = ch; HeapNode
                   
                     N; N.uprofit = up; N.profit = cp; N.weight = cw; N.level = lev; N.ptr = b; H->Insert(N);}template 
                    
                     Typep Knap
                     
                      ::MaxKnapsack(){ //优先队列式分支限界法，返回最大价值，bestx返回最优解 //定义最大堆的容量为1000 H = new MaxHeap< HeapNode
                      
                        >(1000); //为bestx分配存储空间 bestx = new int [n+1]; //初始化 int i=1; E= 0; cw = cp = 0; Typep bestp = 0; Typep up = Bound(1); //搜索子集空间树 while(i!=n+1)//非叶节点 { //检查当前扩展结点的左儿子结点 Typew wt = cw + w[i]; if(wt <= c) { if(cp+p[i] > bestp) bestp = cp+p[i]; AddLiveNode(up,cp+p[i],cw+w[i],true,i+1); } up = Bound(i+1); //检查扩展结点的右儿子结点 if(up >= bestp)//右子树 可能含有最优解 AddLiveNode(up,cp,cw,false,i+1); //取得下一扩展点 HeapNode
                       
                         N; H->DeleteMax(N); E = N.ptr; cw = N.weight; cp = N.profit; up = N.uprofit; i = N.level; } //构造当前最优解 for(int j=n;j>0;j--) { bestx[j] = E->LChild; E = E->parent; } return cp;}template 
                        
                         Typep Knapsack(Typep p[],Typew w[],Typew c,int n,int bestx[]){ Typew W = 0; Typep P = 0; //按 单位重量价值 排序 Object * Q = new Object [n]; for(int i=1;i<=n;i++) { Q[i-1].ID = i; Q[i-1].d = 1.0*p[i]/w[i]; P += p[i]; W += w[i]; } if(W<=c) return P; Sort(Q,n); Knap
                         
                           K; K.p = new Typep[n+1]; K.w = new Typew[n+1]; for(int i=1;i<=n;i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = p[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.c = c; K.n = n; Typep bestp = K.MaxKnapsack(); for(int j=1;j<=n;j++) { bestx[Q[i-1].ID] = K.bestx[j]; cout<
                          
                           <
                           
                            >n>>m; cout<<"请依次输入想要输入的物品重量 及 价值"<
                            
                             >w[i]>>p[i]; Knapsack(w,p,m,n,best); return 0;}

本文转自博客园xingoo的博客，原文链接：，如需转载请自行联系原博主。