1. 普通多重背包

把每种物品拆成一个一个的单个的物品,跑01背包。
复杂度:$O(n×m)$(物品数量×背包容量)

2. 多重背包的二进制优化

你把一种物品拆成一个一个的物品累不累啊?
我们知道,用二进制可以表示任何数字,即$2^0,2^1,2^2...$到$2^k$可以表示1到$2×(2^k)-1$内的所有整数。
这就是二进制优化的原理。
我们同样是把某种物品拆开,但我们不一个一个拆。
比如有一类物品数量为$x$,我们把它拆成一组一组的。
第一组有$1$个物品
第二组有$2$个物品
第三组有$4$个物品
第四组有$8$个物品
......
倒数第二组有$2^k$个物品($2^k<x$)
最后一组有$x-2^k$个物品

这一组一组组合起来,一定能表示所有的1到$x$之间的所有数字。

然后我们把每一组看做一个物品。最多有$log2(x)$个物品。

比如$x=10$,我们就把这种物品这样分成4组:$1,2,4,3$
然后不难发现这个东西:

要在这种物品中选的物品数 组合方法
1 1
2 2
3 3
4 4
5 1+4
6 2+4
7 1+2+4
8 1+3+4
9 2+3+4
10 1+2+3+4

组合方法不一定只有这些。
可以证明,这样拆分可以表示所有的要选的物品数。
这样我们就实现了二进制优化了。

具体看代码吧。。。

例题&代码

Coins HDU - 2844
传送门= ̄ω ̄=

题解:
这题就是多重背包的二进制拆分。
状态转移方程:
$f(i)=max(f(i),f(i-a[j])),f(0)=1$
最后输出$f$的总和。
用普通的多重背包会TLE。所以要二进制拆分。

代码: