54-算法解析及优化拓展

4.9.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：算法中有主要的是两层嵌套的for循环，其时间复杂度为O(n*W)。

（2）空间复杂度：由于二维数组c[n][W]，所以空间复杂度为O(n*W)。

2．算法优化拓展

如何实现优化改进呢？首先有一个主循环i=1，2，…，N，每次算出来二维数组c[i][0～W]的所有值。那么，如果只用一个数组dp[0～W]，能不能保证第i次循环结束后dp[j]中表示的就是我们定义的状态c[i][j]呢？c[i][j]由c[i−1][j]和c[i−1] [j−w[i]]两个子问题递推而来，能否保证在递推c[i][j]时（也即在第i次主循环中递推dp[j]时）能够得到c[i−1][j]和c[i−1][j−w[i]]的值呢？事实上，这要求在每次主循环中以j=W，W−1，…，1，0的顺序倒推dp[j]，这样才能保证递推dp[j]时dp[j−c[i]]保存的是状态c[i −1][j−w[i]]的值。

伪代码如下：

for i=1..n 
for j=W..0 
       dp[j]=max{dp[j],dp[j-w[i]]+v[i]};

其中，dp[j]=max{dp[j]，dp[j−w[i]]}就相当于转移方程c[i][j]=max{c[i−1][j]，c[i−1][j− w[i]]}，因为这里的dp[j−w[i]]就相当于原来的c[i−1][j−w[i]]。

//program 4-7-1
#include <iostream>
#include<cstring>
using namespace std;
#define maxn 10005
#define M 105
int dp[maxn];    //dp[j] 表示当前已放入容量为j的购物车获得的最大价值
int w[M],v[M];   //w[i] 表示第i个物品的重量，v[i] 表示第i个物品的价值
int x[M];        //x[i]表示第i个物品是否放入购物车
int i,j,n,W;     //n表示n个物品，W表示购物车的容量
void opt1(int n,int W)
{
      for(i=1;i<=n;i++)
          for(j=W;j>0;j--)
               if(j>=w[i])  //当购物车的容量大于等于物品的重量，比较此物品放与不放是否能使得购物车内的价值最大
                  dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
int main()
{
     cout << "请输入物品的个数 n:";
     cin >> n;
     cout << "请输入购物车的容量W:";
     cin >> W;
     cout << "请依次输入每个物品的重量w和价值v,用空格分开:";
     for(i=1;i<=n;i++)
          cin>>w[i]>>v[i];
     for(j=1;j<=W;j++)//初始化第0行为0
          dp[j]=0;
     opt1(n,W);
     //opt2(n,W);
     //opt3(n,W);
     cout<<"装入购物车的最大价值为:"<<dp[W]<<endl;
     //测试dp[]数组结果
     for(j=1;j<=W;j++)
          cout<<dp[j]<<"  ";
     cout<<endl;
     return 0;
}

其实我们可以缩小范围，因为只有当购物车的容量大于等于物品的重量时才要更新（dp[j] = max（dp[j],dp[j−w[i]]+v[i]）），如果当购物车的容量小于物品的重量时，则保持原来的值（相当于原来的c[i−1][j]）即可。因此第2个for语句可以是for(j=W；j>=w[i]；j−−)，而不必搜索到j=0。

void opt2(int n,int W)
{
      for(i=1;i<= n;i++)
          for(j=W;j>=w[i];j--)
               //当购物车的容量大于等于物品的重量，比较此物品放与不放是否能使得购物车内的价值最大
               dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}

我们还可以再缩小范围，确定搜索的下界bound，搜索下界取w[i]与剩余容量的最大值，sum[n] −sum[i−1]表示i～n的物品重量之和。W−（sum[n] −sum[i−1]）表示剩余容量。

因为只有购物车容量超过下界时才要更新（dp[j] = max（dp[j]，dp[j−w[i]]+v[i]）），如果购物车容量小于下界，则保持原来的值（相当于原来的c[i−1][j]）即可。因此第2个for语句可以是for(j=W；j>=bound；j−−)，而不必搜索到j=0。

void opt3(int n,int W)
{
      int sum[n];//sum[i]表示从1~i的物品重量之和
      sum[0]=0;
      for(i=1;i<=n;i++)
           sum[i]=sum[i-1]+w[i];
      for(i=1;i<=n;i++)
      {
           int bound=max(w[i],W-(sum[n]-sum[i-1]));//搜索下界，w[i]与剩余容量取最大值,sum[n]-sum[i-1]表示从i...n的物品重量之和
           for(j=W;j>=bound;j--)
               //购物车容量大于等于下界，比较此物品放与不放是否能使得购物车内的价值最大
               dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
      }
}