前置知识

概念：什么是多重背包

相较于01背包和完全背包，更实际的，多重背包是每一个物品有个数限制的背包，这相较于前面两个就有一点点难度了

思路：设计多重背包

首先，最最最基础的，我们可以像完全背包那样，暴力枚举每一个物品选多少次，代码时间复杂度是三次方的。

for(int i = 1; i <= n; i++) // 枚举物品
    for(int j = 0; j <= v; j++) // 枚举体积
        for(int k = 0; k <= s[i] && k * c[i] <= j; k++) // 枚举决策
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * c[i]] + k * w[i]);

那么，我们考虑更优的方式去选择物品。

当你面对一些奇奇怪怪的优化分组没有思路的时候，你就可以稍微考虑考虑二进制。二进制拆分，因为二进制转变为十进制的唯一性，所以我们对于物品数量二进制拆分可以优化到 $O(n\log n)$ ，代码如下：

for(int i = 1; i <= n; i++) {
    int a, b, s; 
    scanf("%d%d%d", &a, &b, &s);
    //倍增思想 
    int k = 1; //相当于base(每组件数)：1 2 4 8 16 32 64 128 256...据此打包
    while(k <= s) {
        cnt++;
        c[cnt] = k * a;
        w[cnt] = k * b;
        s -= k;
        k *= 2;
    }
    if(s > 0) { //若拆完之后还有零头
        cnt++; //再分一个包
        c[cnt] = a * s;
        w[cnt] = b * s;
    }
}
//相当于将多重背包转化为01背包
for(int i = 1; i <= cnt; i++) 
    for(int j=v; j >= c[i]; j--)//注意倒序遍历（参考优化后的01背包）
        dp[j]=max(dp[j],dp[j-c[i]]+w[i]);