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$
然后不难发现这个东西：

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

具体看代码吧。。。

例题&代码

Coins HDU – 2844
传送门＝￣ω￣＝

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

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt,arr[105],a[100005],ans;
bool book[100005];
int main()
{
    while(scanf("%d%d",&n,&m),n|m)
    {
        memset(book,0,sizeof(book)),book[0]=1,cnt=ans=0;
        for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
        for(int i=1,k,l;i<=n;i++)
        {
            scanf("%d",&k),l=1;
            while(k>l)a[++cnt]=arr[i]*l,k-=l,l<<=1;
            a[++cnt]=arr[i]*k;
        }
        for(int i=1;i<=cnt;i++)
            for(int j=m;j>=a[i];j--)
                if(book[j-a[i]])book[j]=1;
        for(int i=1;i<=m;i++)if(book[i])ans++;
        printf("%d\n",ans);
    }
    return 0;
}