我们都知道01背包核心代码是:
for(int i=0;i<n;i++)
for(int j=m;j>=v;j--)
dp[j]=max(dp[j],dp[j-v]+w);
而完全背包核心代码是:
for(int i=0;i<n;i++)
for(int j=v;j<=m;j++)
dp[j]=max(dp[j],dp[j-v]+w);
可以看到俩者的区别只有枚举体积的时候的是正序还是逆序的差距(也就是从大到小还是从下到大)
那么为什么从大到小枚举的时候是01背包呢?逆序为什么不能是01背包呢?
回到01背包的特点:每个物品至多选一次!(只有选或我们不选)
我们先来看正序为什么不行
给个错误的样例可能就你很明确了。
进行第一次循环,第一个物品的体积和价值均为4,背包容积就来个100吧!
也就是此时m=100,v=4,i=1;
代入正序的代码打个表就可以得到一下数据了
dp[4]=max(dp[4],dp[0]+w);
dp[5]=max(dp[5],dp[1]+w);
dp[6]=max(dp[6],dp[2]+w);
dp[7]=max(dp[7],dp[3]+w);
dp[8]=max(dp[8],dp[4]+w);
dp[9]=max(dp[9],dp[5]+w);
.....
dp[100]=max(dp[100],dp[96]+w);
有没有发现什么?
我们来看dp[8],如果他择优到dp[4]+w,那么dp[4]我们是不是在i=1这一轮以及在更新dp[8]之前更新过了,如果dp[4]已经择优到dp[0]+w,那么就等价于dp[8]=dp[4]+w=dp[0]+2*w(选了俩次第一个物品);到这里就可以看出,正序的算法已经违背01背包的特性了,但符合完全背包的特性