二进制拆分
二进制拆分是对多重背包的一种优化方式，可以极大的优化多重背包的时间。
原理
一个数可以被拆分为任意二进制的和。
例如：$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] )\) 。