二进制拆分

二进制拆分是对多重背包的一种优化方式，可以极大的优化多重背包的时间。

原理

一个数可以被拆分为任意二进制的和。

例如：$7= 2^0 + 2^1 +2^2 $

任意一个数都可以表示为几个 \(2\) 的多少次方之和的形式。

我们回顾下完全背包问题。

背包容积为 \(C\) , 有 \(n\) 种物品 , 每种物品有 \(k[i]\) 个, 第 \(i\) 个物品占用 \(w[i]\) 的容积，价值为 \(v[i]\) 。问能用背包装进的物品和的最大值。

常规做法是将其转化成01背包来做，时间复杂度为：\(O(C \times \sum_{1}^{n} k[i] )\) 。

实现