参考文献：

视频链接b站：

https://b23.tv/GUZU6z

时间复杂度分析：

朴素的多重背包解法为：O(nms)
二进制优化：O(n m logs)
单调队列优化:O（nm）

状态表示：f[i][j]

前i个物品中，选择总体积不超过j的选法中价值最大的值。

状态计算 //(其中v为体积，w为价值)

选择a[i] ---> 0个
选泽a[i] ---> 1个
.....
选择a[i] ---> s个（s为限制）

则：f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i]) //(k 从0到s， 当然j - k * v[i] 要 >= 0才行)

朴素版的多重背包代码实现（1维方式） ---->作为单调队列优化的对照模板

for(int i = 1 ; i <= n ; i++)
{
    for(int j = m ; j >= v ; j--)
    {
        for(int k = 1 ; k <= s && j >= k * v ; k++)
        {
            f[j] = max(f[j],f[j - k * v] + k * w);
            printf("f[%d]=%2d f[%d]+%d=%d \n",j,f[j],j - k*v,k*w,f[j-k*v]+k*w);
        }
    }
}

printf("%d\n",f[m]);  //f[m]的含义就是f[n][m]

由上面代码的 printf的结果 看规律：（printf()输出的含义是f[temp] 由什么数据影响了它）

v:3  w:5 s: 2
f[9]= 5 f[6]+5=5
f[9]=10 f[3]+10=10   // 由于s为2所以最多2个

f[8]= 5 f[5]+5=5 
f[8]=10 f[2]+10=10      // 由于s为2所以最多2个

f[7]= 5 f[4]+5=5 
f[7]=10 f[1]+10=10      // 由于s为2所以最多2个

f[6]= 5 f[3]+5=5 
f[6]=10 f[0]+10=10      // 由于s为2所以最多2个

f[5]= 5 f[2]+5=5

f[4]= 5 f[1]+5=5 

f[3]= 5 f[0]+5=5 


v:2  w:4 s: 3
f[9]=14 f[7]+4=14 
f[9]=14 f[5]+8=13 
f[9]=17 f[3]+12=17       // 由于s为3所以最多3个

f[8]=14 f[6]+4=14 
f[8]=14 f[4]+8=13 
f[8]=14 f[2]+12=12        // 由于s为3所以最多3个

f[7]=10 f[5]+4=9 
f[7]=13 f[3]+8=13 
f[7]=13 f[1]+12=12        // 由于s为3所以最多3个

f[6]=10 f[4]+4=9 
f[6]=10 f[2]+8=8 
f[6]=12 f[0]+12=12        // 由于s为3所以最多3个

f[5]= 9 f[3]+4=9 
f[5]= 9 f[1]+8=8        // 由于s为3所以最多3个

f[4]= 5 f[2]+4=4 
f[4]= 8 f[0]+8=8        // 由于s为3所以最多3个

f[3]= 5 f[1]+4=4        // 由于s为3所以最多3个

f[2]= 4 f[0]+4=4        // 由于s为3所以最多3个

于是从这个结果可以发现

发现1：f[temp]是怎么计算得来得：f[temp]由f[temp - v] , f[temp - 2v] , … f[temp - sv]得来

由f[0]，f[v],f[2v],...f[kv]  每一个后面的值由前面的值进行更新而得到。如f[9]由f[7,5,3]得到最终值
f[1],f[1 + v],f[1 + 2v], ... , f[1 + kv];
f[j],f[j + v],f[j + 2v], ... , f[j + kv];

其中j是v的余数。当j == v时，就是f[v]了已经存在有了重复了。  即0 <= j <= v - 1

发现2：f[9]由f[7,5,3]的到， f[11]由f[9,7,5]得到，f[13]由f[11,9,7]得到，所以每次都是找其前面3个中得相应特性（f[i] + (k - i) / v * w）得到f[],所以可以使用滑动窗口也就是单调队列进行优化

同时f[j]是由前面不超过数量s的同类值递推得到的。
如：s = 3

f[9] = 14 , f[7] + 4 = 14
f[9] = 14 , f[5] + 8 = 13
f[9] = 17 , f[3] + 12 = 17 

递推过程每次不会超过3个


这就相当于从前面宽度为s的窗口挑选最大值来更新当前值。 所以可以使用单调队列来维护窗口最大值。

发现3：逆序遍历要改为顺序遍历。 因为滑动窗口的下标是从小到大不断去维护的

为什么要将逆序遍历 改为 顺序遍历 呢？

由于上面朴素模板代码是逆序遍历的。也就是先完成f[4]在完成f[3].因为我们优化成了一维的空间，使得不得不从大到小遍历，因为每次用到的是f[i - 1][j]但是一维时f[j]的含义是f[i][j], 所以用从大到小遍历
for(int j = m ; j >= v ; j--)


而单调队列下标从小到大滑动。那么就需要从小到大进行更新。
也就是先完成了f[3]之后才会去完成f[4]。

即单调队列的这个思路是：
f[9] = 14 , f[7] + 4 = 14
f[9] = 14 , f[5] + 8 = 13
f[9] = 17 , f[3] + 12 = 17 
这个三步，只要知道f[3] + 12,f[5] + 8,f[7] + 4哪个最大之后，直接用这个更新f[9]
所以需要先算出f[3],f[5],f[7]    而不能for(int j = m ; j >= v ; j--)从大到小枚举。

也就是需要顺序更新f值。 也就是要变为for(int j = 1 ; j <= m ; j++)

而想要将逆序变为顺序的话，方式很简单：

只需要增加一个备份数组g[]即可.从大到小for()是因为f[]的小值如果顺序遍历会被更改
所以更改之前存到g[]中，则f[]小值被更改无所谓了。因为要用的f[]小值已经备份到了g[]中


顺序存储实现代码：
for(int i = 1 ; i <= n ; i++)
{
    memcpy(g,f,sizeof f); //将f备份到g中
    for(int j = 1 ; j <= m ; j++)  //改为了顺序遍历
    {
        for(int k = 1 ; k <= s && j >= k * v ; k++)
        {
            f[j] = max(g[j],g[j - k * v] + k * w); //f[j - k * v]已经被修改了。原值在g[j - k * v]中
            printf("f[%d]=%2d f[%d]+%d=%d \n",j,f[j],j - k*v,k*w,f[j-k*v]+k*w);
        }
    }
}

printf()中的结果进行输出

//使得f[i]中i从小到大更新

v:3  w:5  s:2
f[3]= 5 f[0]+5=5 
f[4]= 5 f[1]+5=5 
f[5]= 5 f[2]+5=5 
f[6]= 5 f[3]+5=10 
f[6]=10 f[0]+10=10 
f[7]= 5 f[4]+5=10 
f[7]=10 f[1]+10=10 
f[8]= 5 f[5]+5=10 
f[8]=10 f[2]+10=10 
f[9]= 5 f[6]+5=15 
f[9]=10 f[3]+10=15 



v:2  w:4  s:3
f[2]= 4 f[0]+4=4 
f[3]= 5 f[1]+4=4 
f[4]= 5 f[2]+4=8 
f[4]= 8 f[0]+8=8 
f[5]= 9 f[3]+4=9 
f[5]= 8 f[1]+8=8 
f[6]=10 f[4]+4=12 
f[6]=10 f[2]+8=12 
f[6]=12 f[0]+12=12 
f[7]=10 f[5]+4=12 
f[7]=13 f[3]+8=13 
f[7]=12 f[1]+12=12 
f[8]=14 f[6]+4=16 
f[8]=13 f[4]+8=16 
f[8]=12 f[2]+12=16 
f[9]=14 f[7]+4=16 
f[9]=13 f[5]+8=16 
f[9]=17 f[3]+12=17 

于是从printf()的结果可以发现，从小到大遍历成功

从上面的式子可以看出，如果不想使用逆序，也可以使用g[]进行备份的方式。变成1维。

对两个for()循环代码进行单调队列的优化：

for(int j = 1 ; j <= m ; j++)  //改为了顺序遍历
{
    for(int k = 1 ; k <= s && j >= k * v ; k++)
    {
        f[j] = max(g[j],g[j - k * v] + k * w); //f[j - k * v]已经被修改了。原值在g[j - k * v]中
    }
}

对上面的两个for()循环使用单调队列优化

第一个for()循环：

第一个for()循环改为：

for(int j = 0 ; j < v ; j++) // 拆分成0~v - 1个类。 每个类更新其对应的组中的值。

因为f[t * v] 由g[t * v] (只不过g[t * v]刚开始与f[t * v]相同),g[(t - 1) * v] , g[(t - 2) * v] ... g[(t - s) * v] （s + 1组进行更新，选0个~选s个）
不会被其他的g[]更新， 所以想要更新f[t * v]的最大值，只有在这que[0]组中找到单调队列中的最大值进行更新它即可。

同样因为f[t * v + 1] 由g[t * v + 1]， g[(t - 1) * v + 1] , g[(t - 2) * v + 1] ... g[(t - s) * v + 1]进行更新
所以只要找到单调队列中que[1]这一组的最大值更新它。

第二个for()循环改为

for(int k = j ; k <= m ; k += v) //就是每一个对应的t * v + temp的值。由小到大更新。并存入单调队列中。

其中这个k的含义是当前背包装载的最大重量。

也就是原f[i][j]中的j的含义。

改为单调队列 代码实现：

//其中g[k]的含义是在i中重量为k时一个选0个a[i].

for(int i = 1 ; i <= n ; i++)
{
    memcpy(g,f,sizeof f);
    for(int j = 0 ; j < v ; j++) //拆分成0~v-1这些类
    {
        int h = 0 , t = -1;
        for(int k = j ; k <= m ; k += v) //对每个类使用单调队列。 这个k是什么含义，是当前背包的总重量。 也就是最开始的f[i][j]中的j值，放入一个物品k + v, 直到放不下物品 k <= m
        {
            if(h <= t) //队列不空
            {   //队列q[]中放的是什么呢？ 队列中放的也是重量。1，3，5，7，9. 中重量f[9]由g[7（重量）],g[5（重量）],g[3（重量）]进行更新
                if(q[h] < k - s * v) //k为当下需要求出的f[k]的下标,k - s*v代表队列对头最大的下标值。举例：k == 9, s == 3 ，v == 2时. 则1,3,5,7,9中f[9]只能被g[3],g[5],g[7]进行更新。所以1要踢出队列（队列中存的是下标g[temp]中的temp值）。
                {
                    h++;  //将对出的队头出队。
                }
            }
            if(h <= t) //队列不空. 于是用当前队列中的值去更新f[k].而队列中存的下标q[h]所对应的为最大值。而这个对应是什么呢？并不是g[ q[h] ]最大。 而是对应的值g[ q[h] ] + (k - q[h]) / v * w的值在 队列中最大。因为这个是
            {
                f[k] = max(g[k],g[ q[h] ] + (k - q[h]) / v * w) //g[k]为 一个都不选的情况,而q[h]为的1,3,5,7中（重量为1或者3或者5或者7的时候 价值最大的情况存在队列的头）。现在的重量为k,物品为a[i]. (k - q[h]) / v 为放入多少个a[i]这个物品。 所以在 * w 就是它新增的价值 . 在+g[ q[h] ] (q[h]重量时的价值)。  这最后的最大值就是f[k]的值
            }

            while(h <= t && g[k] >= g[ q[t] ] + (k - q[t]) / v * w) //下一轮的 k1 = k + v的值，而g[k]是什么，g[k]是目前不用a[i]物品用前a[i - 1]个物品达到g[k]的值。 而g[ q[t] ] + (k - q[t]) / v * w  加入(k - q[t]) / v个a[i] 达到k的值。二者进行比较一下当前哪个更有价值，因为下一轮k = k + v 双方可以在当前的基础上（1个加了0个a[i]，一个已经加了(k - q[t]) / v个a[i]）再加一个a[i]的值。如果g[k]大于g[ q[t] ] + (k - q[t]) / v * w那么q[t]变k1的情况一定不会有直接k 变k1的情况要有价值，所以删掉。
            {
                t--; //使得队列中的h[i]，h[i + 1], ...h[i + s - 1]重量 加物品a[i]的(k - h[temp])个的价值从大到小排列。
            }
            q[++t] = k; //加重量为k的情况加入队列，因为下一轮 k1 = k + v ， 用到的是k,以及队列中没有出队的情况
        }
    }
}


printf("%d\n",f[m]);

最后的 完整代码实现：

# include <iostream>
# include <cstring>
using namespace std;

const int N = 1010 , M = 20010;

int w[N],s[N],v[N],g[M],f[M];  //g为备份的f。
int q[M];  //q[]为单调队列

int n,m;

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d %d %d",&v[i],&w[i],&s[i]);
    }

    for(int i =1  ; i <= n ; i++)
    {
        memcpy(g,f,sizeof f);
        for(int j = 0 ; j < v[i] ; j++)
        {
            int hh = 0, tail = -1;
            for(int k = j ; k <= m ; k += v[i])
            {
                if(hh <= tail) //队列不空
                {
                    while(q[hh] < k - s[i] * v[i])
                    {
                        hh++;
                    }
                }
                if(hh <= tail)
                {
                    f[k] = max(g[k] , g[ q[hh] ] + (k - q[hh]) / v[i] * w[i]);
                }
                while(hh <= tail && g[k] >= g[ q[tail] ] + (k - q[tail]) / v[i] * w[i])
                {
                    tail--;
                }
                q[++tail] = k;
            }
        }
    }
    printf("%d\n",f[m]);  //f[m]的含义就是f[n][m];
    return 0;
}