13-算法优化拓展

5.2.7　算法优化拓展

我们在上面的程序中上界函数是当前价值cp与剩余物品的总价值rp之和，这个估值过高了，因为剩余物品的重量很有可能是超过购物车容量的。因此我们可以缩小上界，从而加快剪枝速度，提高搜索效率。

上界函数bound()：当前价值cp+剩余容量可容纳的剩余物品的最大价值brp。

为了更好地计算和运用上界函数剪枝，先将物品按照其单位重量价值（价值/重量）从大到小排序，然后按照排序后的顺序考查各个物品。

//program 5-1-1
#include <iostream>
#include <string>
#include <algorithm>
#define M 105
using namespace std;
int i,j,n,W;       //n表示物品个数，W表示购物车的容量
double w[M],v[M];  //w[i] 表示第i个物品的重量，v[i] 表示第i个物品的价值
bool x[M];         //x[i]=1表示第i个物品放入购物车
double cw;         //当前重量
double cp;         //当前价值
double bestp;      //当前最优值
bool bestx[M];     //当前最优解
double Bound(int i)//计算上界（即将剩余物品装满剩余的背包容量时所能获得的最大价值）
{
      //剩余物品为第i~n种物品
     double cleft=W-cw;//剩余容量
     double brp=0.0;
     while(i<=n &&w[i]<cleft)
     {
          cleft-=w[i];
          brp+=v[i];
          i++;
     }
     if(i<=n) //采用切割的方式装满背包，这里是在求上界，求解时不允许切割
     {
          brp+=v[i]/w[i] *cleft;
     }
     return cp+brp;
}
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);
     }
}
struct Object            //定义物品结构体，包含物品序号和单位重量价值
{
     int id;             //物品序号
     double d;           //单位重量价值
};
bool cmp(Object a1,Object a2)//按照物品单位重量价值由大到小排序
{
     return a1.d>a2.d;
}
void Knapsack(int W, int n)
{
     //初始化
     cw=0;               //初始化当前放入购物车的物品重量为0
     cp=0;               //初始化当前放入购物车的物品价值为0
     bestp=0;            //初始化当前最优值为0
     double sumw=0;      //用来统计所有物品的总重量
     double sumv=0;      //用来统计所有物品的总价值
     Object Q[n];        //物品结构体类型,用于按单位重量价值(价值/重量比)排序
     double a[n+1],b[n+1];//辅助数组,用于把排序后的重量和价值传递给原来的重量价值数组
     for(i=1;i<=n;i++)
     {
          Q[i-1].id=i;
          Q[i-1].d=1.0*v[i]/w[i];
          sumv+=v[i];
          sumw+=w[i];
     }
     if(sumw<=W)
     {
          bestp=sumv;
          cout<<"放入购物车的物品最大价值为: "<<bestp<<endl;
          cout<<"所有的物品均放入购物车.";
          return;
     }
     sort(Q,Q+n,cmp);    // 按单位重量价值(价值/重量比)从大到小排序
     for(i=1;i<=n;i++)
     {
          a[i]=w[Q[i-1].id];//把排序后的数据传递给辅助数组
          b[i]=v[Q[i-1].id];
     }
     for(i=1;i<=n;i++)
     {
          w[i]=a[i];        //把排序后的数据传递给w[i]
          v[i]=b[i];
     }
     Backtrack(1);
     cout<<"放入购物车的物品最大价值为: "<<bestp<<endl;
     cout<<"放入购物车的物品序号为: ";
     for(i=1; i<=n; i++)
     {
          if(bestx[i]==1)
             cout<<Q[i-1].id<<" ";
     }
     cout<<endl;
}
int main()
{
     cout << "请输入物品的个数 n:";
     cin >> n;
     cout << "请输入购物车的容量W:";
     cin >> W;
     cout << "请依次输入每个物品的重量w和价值v,用空格分开:";
     for(i=1;i<=n;i++)
          cin>>w[i]>>v[i];
     Knapsack(W,n);
     return 0;
}

（1）时间复杂度：约束函数时间复杂度为O(1)，限界函数时间复杂度为O(n)。最坏情况下有O(2ⁿ)个左孩子结点调用约束函数，有O(2ⁿ)个右孩子结点需要调用限界函数，回溯算法Backtrack需要的计算时间为O(n2ⁿ)。排序函数时间复杂度为O(nlogn)，这是考虑最坏的情况，实际上，经过上界函数优化后，剪枝的速度很快，根本不需要生成所有的结点。

（2）空间复杂度：除了记录最优解数组外，还使用了一个结构体数组用于排序，两个辅助数组传递排序后的结果，这些数组的规模都是n，因此空间复杂度仍是O(n)。