大家好，又见面了，我是你们的朋友全栈君。
对于背包问题，经典的背包九讲已经讲的很明白了，本来就不打算写这方面问题了。
但是吧。
我发现，那个最出名的九讲竟然没写队列优化的背包。。。。
那我必须写一下咯嘿嘿，这么好的思想。
我们回顾一下背包问题吧。
01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
就是说，对于本物品，我们选择拿或不拿
比如费用是3.
相关图解：
![单调队列优化的背包问题[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
![单调队列优化的背包问题[通俗易懂]](https://img-blog.csdn.net/20181011203334931)
我们求表格中黄色部分，只和两个黑色部分有关
拿了，背包容量减少，我们价值加上减少后最大价值。
不拿，最大价值等于没有这件物品，背包不变，的最大价值。
完全背包问题
题目
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
图解：
![单调队列优化的背包问题[通俗易懂]](https://img-blog.csdn.net/20181011203454149)
因为我们拿了本物品还可以继续拿无限件，对于当前物品，无论之前拿没拿，还可以继续拿，所以是f[i][v-c[i]]+w[i]
换一个角度说明这个问题为什么可以f[i][v-c[i]]+w[i]，也就是同一排。
![单调队列优化的背包问题[通俗易懂]](https://img-blog.csdn.net/20181011203933662)
其实是这样的，我们对于黄色部分，也就是当前物品，有很多种选择，可以拿一个，两个。。。一直到背包容量不够了。
也就是说，可以不拿，也就是J1，可以拿一个，也就是G1+w[i]，也可以拿两个，也就是D1+2w[i]，拿三个，A1+3w[i]。
但是我们看G2，G2其实已经是之前的最大了：A1+2w[i]，D1+w[i]，G1他们中最大的，对么？
既然G2是他们中最大的。
我们怎么求J2？
是不是只要求G2+w[i]和J1的最大值就好了。
因为G2把剩下的情况都保存好了。
多重背包问题 （正文）
题目
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
和之前的完全背包不同，这次，每件物品有最多拿n[i]件的限制。
思路一：我们可以把物品全都看成01背包：比如第i件，我们把它拆成n[i]件一样的单独物品即可。
思路二：思路一时间复杂度太高。利用二进制思路：一个n位二进制，能表示2^n种状态，如果这些状态就是拿了多少物品，我们可以把每一位代表的数都拿出来，比如n[i]=16，我们把它拆成1，2，4，8，1，每一堆物品看成一个单独物品。
为什么最后有个一？因为从0到16有十七种状态，四位不足以表示。我们最后补上第五位1.
把拆出来的物品按01背包做即可。
思路三：我们可以利用单调队列：
https://blog.csdn.net/hebtu666/article/details/82720880
再回想完全背包：为什么可以那么做？因为每件物品能拿无限件。所以可以。而多重背包因为有了最多拿多少的限制，我们就不敢直接从G2中拿数，因为G2可能是拿满了本物品以后才达到的状态 。
比如n[i]=2，如果G2的状态是2w[i]，拿了两个2物品达到最大值，我们的J2就不能再拿本物品了。
如何解决这个问题？就是我给的网址中的，双端单调队列
利用窗口最大值的思想。
大家想想怎么实现再看下文。
发现问题了吗？
![单调队列优化的背包问题[通俗易懂]](https://img-blog.csdn.net/20181012084121535)
我们求出J2以后，按原来的做法，是该求K2的，但是K2所需要的信息和J2完全不同，红色才是K2可能需要的信息。
所以我们以物品重量为差，先把黑色系列推出来，再推红色系列，依此类推。
这个例子就是推三次，每组各元素之间差3.
这样就不会出现构造一堆单调队列的尴尬情况了。
在代码中继续详细解释：
//输入
int n;
int W;
int w[MAX_N];
int v[MAX_N];
int m[MAX_N];
int dp[MAX_N+1];//压空间，本知识参考https://blog.csdn.net/hebtu666/article/details/79964233
int deq[MAX_N+1];//双端队列，保存下标
int deqv[MAX_N+1];//双端队列，保存值队列存的就是所有上一行能取到的范围，比如对于J2，队列里存的就是G1-w[i]，D1-2w[i]，A1-3w[i]等等合法情况。（为了操作方便都是j，利用差实现最终的运算）
他们之中最大的就是队头，加上最多存储个数就好。
void solve()
{
for(int i=0;i<n;i++)//参考过那个网址第二题应该懂
{
for(int a=0;a<w[i];a++)//把每个分组都打一遍
{
int s=0;//初始化双端队列头尾
int t=0;
for(int j=0;j*w[i]+a<=W;j++)//每组第j个元素
{
int val=dp[j*w[i]+a]-j*v[i];
while(s<t && deqv[t-1]<=val)//直到不改变单调性
t--;
deq[t]=j;
deqv[t]=val;
t++;
//利用队头求出dp
dp[j*w[i]+a]=deqv[s]+j*v[i];
if(deq[s]==j-m[i])s++;//检查过期
}
}
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/152966.html原文链接：https://javaforall.net
