0-1背包的滚动数组优化

每一次c[i][j]改变的值只与c[i-1][x] {x:1...j}有关c[i-1][x]是前一次i循环保存下来的值，因此，可以将c缩减成一维数组，可以把二维数组变成一维数组减少内存。

for(i=1;i<=num;i++)
  for(j=w;j>=d[i].wi;j--)
      dp[j]=max(dp[j],dp[j-d[i].wi]+d[i].pi);

状态转移方程转换为 c[j] = max(c[j], c[j-w[i]]+v[i]);
并且，我们注意到状态转移方程，每一次推导c[i][j]是通过c[i-1][j-w[i]]来推导的，而不是通过c[i][j-w[i]]（所以完全背包是从小到大的）
因此，j的扫描顺序应该改成从大到小
否则，第i次求c数组，必然先求的c[j-w[i]]的值(即c[i][j-w[i]])，再求c[j](即c[i][j])的值
由于j递增,那么状态方程就成为下面这个样子了
c[i][j] = max(c[i-1][j], c[i][j-w[i]]+v[i])显然不符合题意

多重背包问题

前两种方法就不多说啦…
第三种二进制优化方法：
我们试试看，比如Ci = 14，我们可以把它化成如下4个物品：
重量是Wi，体积是Vi
重量是2 Wi , 体积是2 Vi
重量是4 Wi , 体积是4 Vi
重量是7 Wi , 体积是7 Vi
注意最后我们最后我们不能取，重量是8 Wi , 体积是8 Vi 因为那样总的个数是1 ＋ 2 ＋ 4 ＋ 8 ＝ 15个了，我们不能多取对吧？
我们用这4个物品代替原来的14个物品，大家可以试试原来物品无论取多少个，重量和体积都可以靠我们这几个物品凑出来，这说明我们这种分配方式和原来是等价的。

这样就可以把问题转化为0-1背包问题了…

那为什么是等效的呢？？？

其实还有更快的方法…从Ci/2开始循环，那样循环的次数就少了。

完全背包问题

for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j>=need[i])dp[i][j]=max(dp[i-1][j],dp[i][j-need[i]]+value[i]);
else dp[i][j]=dp[i-1][j];


for(int i=0;i<n;i++)  
for(int j=need[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-need[i]]+value[i]);