试采用分支限界法的求解策略 实现0／1背包问题求解过程。

(1)数据结构
   #define N 8
   #define M 110
   #define MAXNUM 500
   struct Node{
       int x[N];    /*物体的存取状况(-1表示尚未考虑,0表示不取,1表示取)*/
       double u,1;    /*收益上、下界*/
       int wx,px;    /*当前背包内物品的总重量和总价值*/
   };
   typedef struct Node DataType;
   struct SeqQueue{    /*顺序队列*/
       DataType q[MAXNUM];
       int f,r;
   };
   typedef struct SeqQueue*PSeqQueue;/*指向顺序队列的指针类型*/
   (2)思路
   该问题的解空间树是一棵高度为n的完全二叉树,其结点类型为structNode。
   struct Node{
       int x[N];    /*物体的存取状况(-1表示尚未考虑,0表示不取,1表示取)*/
       double u,1;    /*收益上、下界*/
       intwx,px;    /*当前背包内物品的总重量、总价值*/
   }
   需要对这一解空间树进行系统搜索，采用分支限界法来求解。
   算法大体步骤为：
   ①建立一个队列，其数据类型为struct Node型。计算当前总的收益下界，并将解空间树的根结点入队列(其数组x的每个元素均为-1，总重量wx、总价值px均为0)。
   ②循环执行下列程序段，直至队头元素是解空间树的一个叶结点(这等价于队列的每个元素都是解空间树的一个叶结点)：
   取出队头的元素，这个元素是解空间树上的一个非叶结点。若此结点的收益上界小于当前总的收益下界，则去掉该结点(即剪枝)。否则，将解空间树上此结点的左右子女(找到左右子女的方法是：找出此结点的x数组中值是-1的第一个位置，然后把这个-1分别换为1和0，x数组中的其他数据不变，再分别计算收益上下界，总重量和总价值，这样便得到了左右子女)入队列，并刷新当前总的收益下界，假若它们的总重量没有超过题目所给的总重量m且它们的收益上界不小于当前总的收益下界。
   ③队列中总价值最大的元素即为该背包问题的解。
   (3)算法
   intknap branch(intn,int m,int*w,int*p,int*x){
   /*用分支限界法求解0/1背包问题*/
       Node temp,left,right;
       PSeqQueue paqu=createEmptyQueue_seq();
       int i,maxp;
       double low;    /*当前总的收益下界*/
       for(i=0;i＜n;i++)    /*给x数组赋初值-1*/
           temp.x[i]=-1;
       u_and_1(&temp,p,w,n,m);
       /*计算结点的价值上下界及总重量、总价值*/
       low=temp.1：
       /*当前总的收益下界置为解空间树的根结点的收益下界*/
       enQueue_seq(paqu,temp);  /*解空间树的根结点入队列*/
       while(!isnnish(paqu,n)){
       /*如果队头元素不是解空间树的叶结点,则循环*/
           temp=frontQueue_seq(paqu);  /*取队头元素*/
           deQueue_seq(paqu);    /*出队列*/
           if(temp.u＜low)continue;
           /*该结点的收益上界小于当前总的收益下界,剪枝*/
           left=right=temp;
           for(i=0;i＜n;i++)
               if(temp.x[i]==-1)break;
           left.x[i]=0;
           right.x[i]=1;
           u_and_l(&left,p,w,n,m);
           u_and_l(&right,p,w,n,m);
           if(left.wx＜=m&&left.u＞=low){
               enQueue_seq(paqu,left);    /*左子女入队列*/
               if(left.1＞low)low=left.1;    /*刷新当前总的收益下界*/
           }
           if(right.wx＜=m&&right.u＞=low){
               enQueue_seq(paqu,right); /*右子女入队列*/
               if(right.1＞low)low=right.1;/*刷新当前总的收益下界*/
           }
       }
       maxp=-1;
       while(!isEmptyQueue seq(paqu)){
           temp=frontQueue_seq(paqu);    /*取队头元素*/
           deQueue_seq(paqu);    /*出队列*/
           if(temp.px＞maxp){
               maxp=temp.px;
               for(i=0;i＜n;i++)x[i]=temp.x[i];
           }
       }    /*找出队列中总价值最大的元素*/
       free(paqu);
       return maxp;
   }
   void u_and_l(DataType*pdata,int*p,int*w,int n,int m){
   /*子算法。计算结点的收益上下界、总重量和总价值*/
       int i,j,record[N],weight;
       double a[N],b[N];
       pdata-＞px=0：
       pdata-＞wx=0：
       for(i=0;i＜n;i++)
           record[i]=pdata-＞x[i];
       for(i=0;i＜n;i++)
           if(record[i]==1){
               pdata-＞px+=p[i];
               pdata-＞wx+=w[i];
           }
       pdata-＞u=pdata-＞l=pdata-＞px;
       weight=pdata-＞wx：
       if(pdata-＞wx＞m)return;
       for(i=0;i＜n;i++)
           a[i]=b[i]=((double)(p[i]))/w[i];
       order(a,n);    /*排序*/
       for(i=0;i＜n;i++)
           for(j=0;j＜n;j++)
         if(b[j]==a[i]&&record[j]==-1)
           if((weight+w[j])＞m){
               pdata-＞u+=(double)((m-weight)*p[j]/w[j]);
               weight=m：
           }
           else{
               record[j]=1;
               pdata-＞u+=p[j];
               pdata-＞1+=p[j];
               weight+=w[j];
           }
   }
   int isflnish(PSeqQueue paqu,int n){
   /*子算法。判断队头元素是否解空间树的叶结点。是返回1,否返回0*/
       inti;
       for(i=0;i＜n;i++)
           if(frontQueue_seq(paqu).x[i]==-1)return 0;
       return 1;
   }
   void order(double*a,int n){  /*子算法。对数组a进行冒泡排序*/
       inti,j;
       double temp;
       for(j=0;j＜n-1;j++)
         for(i=0;i＜n-j;i++)
           if(a[i]＜a[i+1]){
               temp=a[i];
               a[i]=a[i+1];
               a[i+1]=temp;
           }
   }
   (4)代价分析
   在此算法中，用贪心法求价值上下界的时候，所花费的时间代价是O(n2)，而其他的过程的时间代价均是O(n)，故时间代价是O(n2)。