多重背包可以看作01背包的拓展， 01背包是选或者不选。多重背包是选0个一直到选s个。
for (int i = 1; i <= n; ++i)
{
for (int j = m; j >= w[i]; --j)
{
f[j] = max(f[j], f[j - 1*w[i]] + 1*v[i], f[j - 2*w[i]] + 2*v[i],...f[j - s*w[i]] + s*v[i]);
}
}由上述伪代码可以得知，要实现的多重背包只需要多加一层循环就可以了。
所得的f[m]就是最大价值。
//多重背包
#include<iostream>
using namespace std;
const int N = 110;
int f[N], n, m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
int w, v, s; cin >> w >> v >> s;//重量，体积，数量
for (int j = m; j >= w; --j)
{
for (int k = 1; k <= s && k * w <= j; ++k)
{
f[j] = max(f[j], f[j - k * w] + k * v);
}
}
}
cout << f[m] << '\n';
return 0;
}上述代码中就是套了一个01背包代码的框架，第三层循环中的 && k * w <= j可以减少不必要的步骤，优化时间。这种方法的时间复杂度为O(n^3)，当数据过大的时候时间就会超限。所以接下来有一种求解数据大一些的求解多重背包的算法(多重背包的二进制优化)。
二进制优化的思想是将s个物品分解为log2(s）份，每份都是2的整次的这个个数。然后问题就会变成01背包问题。
//多重背包2
//二进制优化
#include<iostream>
#include<vector>
using namespace std;
const int N = 2e3 + 9;
int f[N], n, m;
struct Good
{
int v, w;
};
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
vector<Good> goods;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
int v, w, s; cin >> v >> w >> s;
//将物品分解成log2(s)份
//例如将至少使用log2(7)上取整个数来表示0到7这些数字
//也就是2^0 2^1 2^2 (1 2 4)
//0：都不选
//1：只选1
// ....
//7：都选
//若该数字的值不是2的次方-1，例如10，则有log2(10)，也就是4个
//(1 2 4 8)，但是这样连不需要表示的11到15都可以表示出来，所以需要用10-1-2-4
//3 - 8 < 0，所以分解为 1 2 4 3
for (int k = 1; k <= s; k *= 2)
{
s -= k;
goods.push_back({ v * k, w * k });
}
if (s > 0) goods.push_back({s * v, s * w});
}
for (auto g : goods)
{
for (int j = m; j >= g.v; --j)
{
f[j] = max(f[j], f[j - g.v] + g.w);
}
}
cout << f[m];
return 0;
}
重点：01背包是n个物品每样一个 所以一共是n*1个物品 这里是n个物品每样最多s[i]个 所以总共最多是Σs[i]个， 把每一组的摊开变成一个一个 再进行01背包。也就是上述代码中的注释的选和不选。
二进制优化参考：AcWing 5. 二进制优化，它为什么正确，为什么合理，凭什么可以这样分？？ - AcWing
