题目描述

看到有人问为什么不能先遍历次数s，再遍历体积v。

算法1

原因其实很简单，首先需要理解为什么01背包的时候可以将
{
f[i][j]=f[i][j-1]
f[i][j]=max(f[i][j],f[i-1][j-v]+w);
}
优化为
f[j]=max(f[j],f[j-v]+w)
因为去掉i这个维度之后，要保证，每次计算f[j]=max(f[j],f[j-v]+w)时，需要f[j-v]对应于原来的f[i-1][j-v]
所以体积从大到小遍历
这里同理，此时的状态转移方程f[j]:仍然代表当前体积为j时，可取到的max,也需要保证f[j-v]对应于原来的f[i-1][j-v]
以一个数组举例：[1,2,3…m]
先遍历体积时：f[j]=max(f[j],f[j-kv]+w*k)可以看到，再j之前的位置上，也就是f[j-kv]仍然是未被更新的状态，满足要求。
但如果是先遍历次数
for(int i=1;i<=k;i++)
{
…
}
我们会发现我们会将f[j-iv]这些更新，当进入下一轮循环时，此时不满足f[j-v]对应于原来的f[i-1][j-v]。

C++ 代码

for(int i=v;i;i–)
{
for(int k=1;k<=s;k++)
if(i>=kv)
f[i]=max(f[i],f[i-kv]+w*k)
}