多重背包是这样的一个问题：
有N种物品，第i种物品的体积为Ci，价值是Wi，但是每种物品的数量都是有限的，为ni。现在有容量为V的背包，请你放入若干物品，使获得的价值尽量大。
朴素算法： 把N种物品逐个拆分，得到Σni个物品，则原问题可转化为01背包求解。这样做的时间复杂度为O(V×Σn)。
或者是在枚举种类的过程中枚举个数k，这样做可以优化空间复杂度，但时间复杂度也是O(V×Σn)。
优化： 我们可以考虑二进制的思想，将第i种物品拆分成若干件物品，可以有（Ci,Wi),(Ci×2,Wi×2),(Ci×4,Wi×4)，等等，每个物品有一个系数，1, 2, 4, 8… 2k-1, n-2k+1 其中，k是满足n-2k+1>0的最大整数。
比如可以用1,2,4,8,5（20-1-2-4-8=5）这5个数进行组合并相加，来得到20以内的任何数。
这样一来，从n件物品就拆分成了至多logn件物品，再转化为01背包问题求解，复杂度降低到O(VΣlogn)。
思考： 实际上还是运用了倍增的思想。
与之前的倍增略有不同的是，这次不再是将给定的K运用二进制编码进行组合（对于给定的K，确对应一个二进制编码，一定可以用2p将其组合出来）。
而是将K以二进制的形式进行拆分，再对拆分后的数进行组合。（保证1~k中的每个数都能由这几个数最多使用一次组合出来）。
例题： Description Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有n种面值的硬币,面值分别为b1, b2,…, bn. 但是每种硬币有数量限制,现在我们想要凑出面值k求最少要用多少个硬币.
Input 第一行一个数 n, 1 <= n <= 200.
接下来一行 n 个整数b1, b2,..., bn, 1 <= b1 < b2 < ... < b n <= 20 000, 第三行 n 个整数c1, c2,..., cn, 1 <= ci <= 20 000, 表示每种硬币的个数. 最后一行一个数k – 表示要凑的面值数量, 1 <= k <= 20 000.Output 第一行一个数表示最少需要付的硬币数
裸的多重背包问题，状态f[i][j]表示用i种硬币凑出j元最少需要多少个硬币。 状态转移方程：f[i][j]=min(f[i-1][j-v[i]]+1,f[i-1][j])。
Code：
#include<cstdio> #include<algorithm> const int maxn=211; int n; int b[maxn],w[maxn*maxn],v[maxn*maxn],f[20011]; int main(){ int cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++){ int c; scanf("%d",&c); int t=1; while(t*2-1<c){ w[++cnt]=t; v[cnt]=t*b[i]; t<<=1; } w[++cnt]=c-(t-1); v[cnt]=b[i]*w[cnt]; } int k; scanf("%d",&k); for(int i=1;i<=k;i++) f[i]=200015; f[0]=0; for(int i=1;i<=cnt;i++) for(int j=k;j>=v[i];j--){ f[j]=std::min(f[j],f[j-v[i]]+w[i]); // printf("f[%d]=%d\n",j,f[j]); } printf("%d",f[k]); return 0; }