我们继续学习「多重背包の优化篇」。
今天我们将学习「多重背包」的另一种优化方式：单调队列优化。
背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。
将「多重背包」简单拆分成「01背包」也同样无法减少状态数量，同时还会增加「扁平化」的运算成本。
这导致了朴素的「多重背包」解决方案复杂度是的，只能解决数量级为的问题。
二进制优化的本质，是对「物品」做分类，使得总数量为的物品能够用更小的个数所组合表示出来。
而单调队列优化，某种程度上也是利用「分类」实现优化。只不过不再是针对「物品」做分类，而是针对「状态」做分类。
有种物品和一个容量为的背包，每种物品「数量有限」。
第件物品的体积是，价值是，数量为。
问选择哪些物品，每件物品选择多少件，可使得总价值最大。
其实就是在0-1背包问题的基础上，增加了每件物品可以选择「有限次数」的特点（在容量允许的情况下）。
示例1：
输入:N=2,C=5,v=[1,2],w=[1,2],s=[2,1]输出:4解释:选两件物品1，再选一件物品2，可使价值最大。单调队列优化首先，我们还是使用一维空间优化的定义：代表容量不超过时的最大价值。
当遍历完所有的物品后，就是最优解。
在朴素的多重背包解决方案中，当我们在处理某一个物品从到的状态时，每次都是通过遍历当前容量能够装多少件该物品，然后从所有遍历结果中取最优。
但事实上，转移只会发生在「对当前物品体积取余相同」的状态之间。
举个，假设当前我们处理到的物品体积和价值均为，数量为，而我们背包容量为。
那么我们转移到时，其实存在如下规律：
即某个状态只能由相同（为当前物品体积，为当前背包容量），并且比小，数量不超过「物品个数」的状态值所更新。
因此这其实是一个「滑动窗口求最值」问题。
如果我们能够在转移时，以或者均摊的复杂度从「能够参与转移的状态」中找到最大值，我们就能省掉「朴素多重背包」解决方案中最内层的“决策”循环，从而将整体复杂度降低到。
具体的，我们定义一个数组，用来记录上一次物品的转移结果；定义一个数组来充当队列，队列中存放本次转移的结果。
由于我们希望在复杂度内取得「能够参与转移的状态」中的最大值，自然期望能够在对队列头部或者尾部直接取得目标值来更新。
我们发现如果希望始终从队头取值更新的话，需要维持「队列元素单调」和「特定的窗口大小」。
代码：
classSolution{publicintmaxValue(intN,intC,int[]s,int[]v,int[]w){int[]dp=newint[C+1];int[]g=newint[C+1];//辅助队列，记录的是上一次的结果int[]q=newint[C+1];//主队列，记录的是本次的结果//枚举物品for(inti=0;i 与对「物品」做拆分的「二进制优化」不同，「单调队列优化」是对「状态」做拆分操作。 利用某个状态必然是由余数相同的特定状态值转移而来进行优化。 单调队列优化是三种传统背包问题中最难的部分。 不过这里所谓的难，也主要是针对当年楼教主提出这个优化思路的那个年代而言。 这些年，这种根据“取余”对状态做划分，然后转换为「滑动窗口」问题，配合某种数据结构（单调队列/哈希表）来实现优化的方式，早就出现在各种题目中了。