01背包与完全背包的枚举顺序的不同处

2018-09-13 07:11:24


01背包与完全背包的枚举顺序的不同处

顺序枚举

此时我们手中有一件体积为2,价值为6的物品.

很明显我们可以得到一个填充了2体积,价值为6的背包.(黑色代表体积,红色代表价值.

(中间填充3的过程略过 emmm

此时当我们填充到体积为4的背包的时候,我们发现可以通过填充体积为2的背包得到更大价值.

但是,我们手中只有一件这样的物品,再去填充不就违反了题目规定?

同理,当我们枚举到更大体积的时候,依旧不满足要求.

所以,顺序枚举体积是完全背包做法.(即物品有很多件.

倒叙枚举

其实根据上面应该不难理解,但是既然说到这里,我还是决定写一下.

同样,我们依旧有一个体积为2的物品。

此时倒叙,我们填充背包.(依旧是到4.

我们发现,我们还是可以通过填充体积为2的背包得到体积为4的背包.

不过这个时候,体积为2的背包中并没有物品.

因此,我们填充体积得到的4的背包,只是得到了体积为2的物品的价值.

再度枚举到体积为2的背包时,我们才填充得到体积为2的背包.

而接下来枚举到的物品中,不会再重复使用这一件物品.

即最终的图会是这样(其他部分略过.

这样我们就能满足题目中的,每个物品只有一件的情况.

而这也是我们01背包倒叙枚举体积的原因.