10-伪代码详解

6.2.4　伪代码详解

（1）根据算法设计中的数据结构，我们首先定义一个结点结构体Node。

struct Node      //定义结点。每个节点来记录当前的解信息。
{
     int cp, rp; //cp背包的物品总价值，rp剩余物品的总价值
     int rw;     //剩余容量
     int id;     //物品号
     bool x[N];  //解向量
     Node() { memset(x, 0, sizeof(x)); }//解向量初始化为0
     Node(int _cp, int _rp, int _rw, int _id){
          cp = _cp;
          rp = _rp;
          rw = _rw;
          id = _id;
     }
};

在结构体中构造函数Node（int _cp，int _rp，int _rw，int _id）是为了传递参数方便，可以参考2.6.6节明确为什么要使用构造函数。

（2）再定义一个物品结构体Goods

我们在前面处理购物车问题时，使用了两个一维数组w[]、v[]分别存储物品的重量和价值，在此我们使用一个结构体数组来存储。

struct Goods
{
     int weight;
     int value;
} goods[N];

（3）构建函数bfs进行子集树的搜索

首先创建一个普通队列（先进先出），然后将根结点加入队列中，如果队列不空，取出队头元素livenode，得到当前处理的物品序号，如果当前处理的物品序号大于n，说明搜到最后一个物品了，不需要往下搜索。如果当前的购物车没有剩余容量（已经装满）了，也不再扩展。如果当前放入购物车的物品价值大于等于最优值（livenode.cpbestp），则更新最优解和最优值。

判断是否约束条件，满足则生成左孩子，判断是否更新最优值，左孩子入队，不满足约束条件则舍弃左孩子；判断是否满足限界条件，满足则生成右孩子，右孩子入队，不满足限界条件则舍弃右孩子。

int bfs()
{
     int t,tcp,trp,trw;        //当前处理的物品序号t，当前装入购物车物品价值tcp，
                               //当前剩余物品价值trp，当前剩余容量trw
     queue<Node> q;            //创建一个普通队列（先进先出）
     q.push(Node(0, sumv, W, 1)); //压入一个初始结点
     while(!q.empty())         //如果队列不空
     {
          Node livenode, lchild, rchild;//定义3个结点型变量
          livenode=q.front();  //取出队头元素作为当前扩展结点livenode
          q.pop();             //队头元素出队
          t=livenode.id;       //当前处理的物品序号
          // 搜到最后一个物品的时候不需要往下搜索。
          // 如果当前的购物车没有剩余容量（已经装满）了，不再扩展。
          if(t>n||livenode.rw==0)
          {
               if(livenode.cp>=bestp)//更新最优解和最优值
               {
                  for(int i=1; i<=n; i++)
                  {
                    bestx[i]=livenode.x[i];
                  }
                  bestp=livenode.cp;
               }
               continue;
          }
          //判断当前结点是否满足限界条件，如果不满足不再扩展
          if(livenode.cp+livenode.rp<bestp) 
             continue;
          //扩展左孩子
          tcp=livenode.cp;     //当前购物车中的价值
          trp=livenode.rp-goods[t].value; //不管当前物品装入与否，剩余价值都会减少。
          trw=livenode.rw;     //购物车剩余容量
          if(trw>=goods[t].weight) //满足约束条件，可以放入购物车
          {
               lchild.rw=trw-goods[t].weight;
               lchild.cp=tcp+goods[t].value;
               lchild=Node(lchild.cp,trp,lchild.rw,t+1);//创建左孩子结点，传递参数
               for(int i=1;i<t;i++)
               {
                 lchild.x[i]=livenode.x[i];//复制父亲结点的解向量
               }
               lchild.x[t]=true;
               if(lchild.cp>bestp)//比最优值大才更新
                   bestp=lchild.cp;
               q.push(lchild);//左孩子入队
          }
          //扩展右孩子
          if(tcp+trp>=bestp)//满足限界条件，不放入购物车
          {
               rchild=Node(tcp,trp,trw,t+1);//创建右孩子结点，传递参数
               for(int i=1;i<t;i++)
               {
                 rchild.x[i]=livenode.x[i];//复制父亲结点的解向量
               }
               rchild.x[t]=false;
               q.push(rchild);//右孩子入队
          }
     }
     return bestp;  //返回最优值
}