题目：

https://www.acwing.com/problem/content/6/

多重背包问题可以转换为01背包问题

将 S 个数量的物品转换为 S 个单独的物品，然后做01背包问题（然后时间复杂度就爆炸了……）

于是我们就来理解一下多重背包的单调队列做法

原理

f[i][j]=max(f[i−1][j],f[i−1][j−k∗c[i]]+k∗w[i])

其中k∈[1,min(⌊Vc[i]⌋,num[i])]

下面用 lim表示min(⌊Vc[i]⌋,num[i])

容易发现的是f[i][j−k∗c[i]]会被f[i][j−(k+1)∗c[i]]影响 (很明显吧

(我们通过一件体积为c[i]的物品填充体积为j−(k+1)∗c[i]的背包,会得到体积为j−k∗c[i]的背包.)

归纳来看的话

栗子

容易发现的是,同一颜色的格子,对c[i]取模得到的余数相同.

且,它们的差满足等差数列! (公差为c[i].

通项公式为 j=k∗c[i]+取模得到的余数

所以我们可以根据对c[i]取模得到的余数进行分组.

即可分为0,1,2,3…c[i]−1 共c[i]组

且每组之间的状态转移不互相影响.(注意这里是组.相同颜色为一组

相同颜色的格子,位置靠后的格子,将受到位置靠前格子的影响.

//但是这样的话,我们的格子会重复受到影响.(这里不打算深入讨论 害怕误人子弟

即f[9]可能受到f[5]的影响,也可能受到f[1]的影响

而f[5]也可能受到f[1]的影响.

所以我们考虑将原始状态转移方程变形.

重点

令d=c[i],a=j/c[i],b=j%c[i]

其中a为全选状况下的物品个数.

则j=a∗d+b

则带入原始的状态转移方程中

j−k∗d=a∗d+b−k∗d =(a−k)∗d+b
我们令(a−k)=k′

再回想我们最原始的状态转移方程中第二状态 : f[i][j−k∗c[i]]+k∗w[i] 代表选择k个当前i物品.

根据单步容斥 ：全选−不选=选.

因此 a−(a−k)=k

而前面我们已经令(a−k)=k′

而我们要求的状态也就变成了

f[i][j]=max(f[i−1][k′∗d+b]+a∗w[i]−k′∗w[i])

而其中,我们的a∗w[i]为一个常量(因为a已知.)

所以我们的要求的状态就变成了

f[i][j]=max(f[i−1][k′∗d+b]−k′∗w[i])+a∗w[i]

根据我们的

k∈[1,lim]

容易推知

k′∈[a−k,a]

那么

当前的f[i][j]求解的就是为lim+1个数对应的f[i−1][k′∗d+b]−k′∗w[i]的最大值.

(之所以为lim+1个数,是包括当前这个j,还有前面的物品数量.)

将f[i][j]前面所有的f[i−1][k′∗d+b]−k′∗w[i]放入一个队列.

那我们的问题就是求这个最长为lim+1的队列的最大值+a∗w[i].

因此我们考虑到了单调队列优化

(这里不再对单调队列多说.这个题的题解中,有不少讲解此类算法的,如果不会的话还是去看看再来看代码.-->p1886 滑动窗口

//相信你只要仔细看了上面的推导过程,理解下面的代码应该不是很难.

//可能不久的将来我会放一个加注释的代码(不是立flag.

//里面两个while应该是单调队列的一般套路.

for(int i=1;i<=n;i++)//枚举物品种类 
{
    cin>>c[i]>>w[i]>>num[i];//c,w,num分别对应 体积,价值,个数 
    if(V/c[i] <num[i]) num[i]=V/c[i];//求lim
    for(int mo=0;mo<c[i];mo++)//枚举余数 
    {
        head=tail=0;//队列初始化 
        for(int k=0;k<=(V-mo)/c[i];k++) 
        {
            int x=k;
            int y=f[k*c[i]+mo]-k*w[i];
            while(head<tail && que[head].pos<k-num)head++;//限制长度
            while(head<tail && que[tail-1].value<=y)tail--;
            que[tail].value=y,que[tail].pos=x;
            tail++;
            f[k*c[i]+mo]=que[head].value+k*w[i];
            //加上k*w[i]的原因:
            //我们的单调队列维护的是前i-1种的状态最大值.
            //因此这里加上k*w[i].
        }
    }
}

还可以用deque（双端队列）模拟单调队列

#include<bits/stdc++.h>
using namespace std;
int n,m;
int vv,w,s;
int f[20010];
deque< int > v;
deque< int > q;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>vv>>w>>s;
		for(int d=0;d<vv;d++)
		{
			while(v.size())
			{
				v.pop_back();
				q.pop_back();
			}
			int ss=(m-d)/vv;
			for(int j=0;j<=ss;j++)
			{
				int tmp=f[d+j*vv]-j*w;
				while(v.size()&&v.back()<=tmp)a
				{
					v.pop_back();
					q.pop_back();
				} 	
				v.push_back(tmp);
				q.push_back(j);
				while(q.front()<j-s)
				{
					v.pop_front();
					q.pop_front();
				}
				f[d+j*vv]=max(f[d+j*vv],v.front()+j*w);
			}
		}
	}
	cout<<f[m]<<endl;
	return 0;
}

时间复杂度分析

我们做一次单调队列的时间复杂度为O(n)

而对应的每次枚举体积为O(V)

因此总的时间复杂度为O(n∗V)