给出多重背包的一个例题：
这里数据量很小，可以直接暴力去做。可以发现，和01背包例题的主要区别就是每种物品不是固定的一件，而是最多不超过s[i]件，就是所说的 “多重背包是01背包的一个扩展”（在下方的优化方法中会有相应的解释/证明），所以体积在枚举时要从大到小枚举 。
下面讲一下比较重要的三处：
f[i]：总体积是 i 的情况下，最大价值是多少
原始 &未经处理的核心步骤： for(int i=0; i<n; i++) { for(int j=m; j>=v[i]; j- -) f[j] = max(f[j], f[j - v[i]] + w[i], f[j - 2* v[i]] + 2* w[i]…); }
初始化时有两种操作：
如果把所有状态都初始化为 0了，那么f[m]就是答案若只令f[0]=0，其他的都是负无穷，则从f[0~m]中选一个最大值 即： 1.1. f[i]=0。答案：f[m] 2.2. f[0]=0, f[i]=-inf & i!=0。答案：max{f[0… m]} // AC代码 #include <bits/stdc++.h> using namespace std; const int N = 110; int n,m,f[N]; int main() { cin >> n >> m; for(int i=0; i<n; i++) { int v,w,s; cin >> v >> w >> s; for(int j=m; j>=0; j--) for(int k=1; k<=s && k*v<=j; k++) f[j] = max(f[j], f[j-k*v]+k*w); } cout << f[m] << endl; return 0; }当数据量变大时，再去暴力的话，10^9会超时。 需要用到多重背包的二进制优化方法。
为了帮助理解二进制的优化方法，我们先来看一下 “怎么把多重背包问题转化为01背包问题”。
假设第 i 个物品的体积是 v，价值是 w，件数是 s。实际上可以把这个物品拆开，直接拆成s份，每份的体积是 v’，价值是 w’，放到物品堆中去，每份只能用一次，这就变成了一个01背包问题 。
但是这种拆法的复杂度是十分高的，也会达到1e9。那么我们可以考虑如何使得划分的份数减少的同时，还能保证…
我们可以把第 i 种物品分成 logS(以2位底上取整)份 【时间复杂度：1000 x logS x 2000 = 2 x 1e7 】。下面用一个例子来解释：给定任意一个数s，问最少可以把s分成多少个数，使得这些数能组成1~n 的所有数。分成的这些数有2种选法，选和不选，而且它们要能够组成 1~s 的所有数(并且不能凑到>s，即这些数的和不能>s)。
特例： s=7，log7上取整为3。2^0=1 , 2^1=2 , 2^2=4, 1 2 4可以组成1~7所有的数 s=10, log10上取整为4…1 2 4 8。但这4个数的和>10，放不下这么多。 这个时候就在 s 够用的情况下，不断减去前面的数，即得到1 2 4 3 这四个数，经过验证，符合要求。
// AC代码 #include <bits/stdc++.h> using namespace std; const int N = 2010; int n,m,f[N]; struct Good { int v,w; }; int main() { vector<Good> goods; cin >> n >> m; for(int i=0; i<n; i++) { int v, w, s; cin >> v >> w >> s; for(int k=1; k<=s; k*=2) { s -= k; goods.push_back({v*s,w*s}); } if(s>0) goods.push_back({v*s,w*s}); } for(auto good:goods) for(int j=m; j>=good.v; j--) f[j] = max(f[j], f[j-good.v]+good.w); cout<<f[m]<<endl; return 0; }