10-伪代码详解

5.2.4　伪代码详解

（1）计算上界

计算上界是指计算已装入物品价值cp与剩余物品的总价值rp之和。我们已经知道已装入购物车的物品价值cp，剩余物品我们不确定要装入哪些，我们按照假设都装入的情况估算，即按最大值计算（剩余物品的总价值），因此得到的值是可装入物品价值的上界。

double Bound(int i)//计算上界（即已装入物品价值+剩余物品的总价值）
{
     int rp=0; //剩余物品为第i~n种物品
     while(i<=n)//依次计算剩余物品的价值
     {
          rp+=v[i];
          i++;
     }
     return cp+rp;//返回上界
}

（2）按约束条件和限界条件搜索求解

t表示当前扩展结点在第t层，cw表示当前已放入物品的重量，cp表示当前已放入物品的价值。

如果t>n，表示已经到达叶子结点，记录最优值最优解，返回。否则，判断是否满足约束条件，满足则搜索左子树。因为左子树表示放入该物品，所以令x[t]=1，表示放入第t个该物品。cw+=w[t]，表示当前已放入物品的重量增加w[t]。cp+=v[t]，表示当前已放入物品的价值增加v[t]。Backtrack(t+1)表示递推，深度优先搜索第t+1层。回归时即向上回溯时，要把增加的值减去，cw−=w[t]，cp−=v[t]。

判断是否满足限界条件，满足则搜索右子树。因为右子树表示不放入该物品，所以令x[t]=0。当前已放入物品的重量、价值均不改变。Backtrack(t+1)表示递推，深度优先搜索第t+1层。

void Backtrack(int t)     //t表示当前扩展结点在第t层
{
     if(t>n)              //已经到达叶子结点
     {
          for(j=1;j<=n;j++)
          {
               bestx[j]=x[j];
          }
          bestp=cp;       //保存当前最优解
          return ;
     }
     if(cw+w[t]<=W)       //如果满足约束条件则搜索左子树
     {
          x[t]=1;
          cw+=w[t];
          cp+=v[t];
          Backtrack(t+1);
          cw-=w[t];
          cp-=v[t];
     }
     if(Bound(t+1)>bestp) //如果满足限界条件则搜索右子树
     {
          x[t]=0;
          Backtrack(t+1);
     }
}