众所周知，如果完全背包中所有物品大小总和是 $V$ ，那么时间复杂度是 $O(V\sqrt{V})$ 的。

$01$ 背包也类似，但是我以前一直以为要写成多重背包的形式复杂度才是对的。

但实际上可以二进制拆分，时间复杂度也是对的，为什么呢？

证明

首先，拆分中的最后一步，显然只有至多 $O(\sqrt{V})$ 种物品。

现在问题是那些 $2$ 的幂次的情况。

我们不妨考虑最坏情况，选择 $x$ 后，$\frac{x}{2^{i}}$ 全部都贡献了一次。

即对于 $x$ ，选其的贡献是最大的 $k$ ，满足：$x=2^ky$ 。

那么可以发现，这个贡献的数量级小于等于 $\sum\limits_{i=0}\sqrt{\frac{V}{2^{i}}}$ ，所以物品个数还是 $O(\sqrt{V})$ 的。

时间复杂度还是：$O(V\sqrt{V})$ ，比多重背包好写很多。