刷题心得—背包问题的枚举方式

以0/1背包为例，到底正序枚举还是倒序枚举？

正序枚举还是倒叙枚举的原则取决于0/1背包的性质，即一个阶段的状态（1个物品）不能被放进背包两次。如果正序枚举的话，当前阶段被上一个阶段更新，而下一个阶段仍然可能被上一个阶段更新。多以就相当于一个物品被放进了背包两次。违背0/1背包的规则。

而完全背包就不需要考虑这一点，因为物品是无限多个，随便挑最优的往里扔即可。

所以0/1背包必须倒叙枚举，才能保证一个状态不被重复更新。而完全背包需要正序枚举，才能维护一种物品有好多个的这个性质。