2.3　0/1背包算法的优化

在0/1背包问题的状态转移方程f[i][x]=max{f[i-1][x-W[i]]+C[i],f[i-1][x]}中，f[i][x]由上一行的f[i-1][x-W[i]]和f[i-1][x]的值推导而来，因此完全可以将二维数组f[i][x]改为一维数组f[i]来表示。

f[i]数组的下标表示背包的最大承重，数值表示该承重下能装入的物品的最大价值。现在已经装好了第一个物品（W=3，C=3），如图2.1所示。

图2.1

尝试装入第二个物品（W=5，C=4），此时搜索方向应为从后向前，先搜索到下标11，根据公式可以计算出f[11]=f[11-5]+4=7，如图2.2所示。

图2.2

再搜索到下标10，此时下标11里面虽然已经装了第二个物品，但是由于每次计算都只会用到下标小于当前下标的数据，下标11之前的数据都是没有装进第二个物品的状态，因此这是在每个物品最多只能装入一个的情况下计算出来的数据，也就是所谓的0/1背包。

参考代码如下。

 1    //0/1背包 —— 优化算法
 2    #include <bits/stdc++.h>
 3    using namespace std;
 4
 5    int f[10001];
 6
 7    int main()
 8    {
 9      int m,n,w,c;
10      scanf("%d%d",&m,&n);
11      for(int i=1; i<=n; i++) //枚举每个物品
12      {
13        scanf("%d%d",&w,&c);
14        for(int j=m; j>=w; --j)                             //反向枚举背包承重
15          f[j]=max(f[j-w]+c,f[j]);
16      }
17      printf("%d\n",f[m]);
18      return 0;
19    }