终于到了，我每次看到背包九讲就停下来的关键点了。
朴素二维实现-一维实现
多重背包本身是一个比较简单的问题，就是将01背包和完全背包中的物品个数限定为了s[i]个。但是因为这个条件，我们无法无限制的拿取物品也就无法通过一维实现的方式去优化时间复杂度了，同完全背包的二维解法基本上相同，只不过将第三层循环的结束条件做了一点点的改变，改为了k≤s[i]。到这里，内容还很好理解，它的一维优化也基本上和完全背包一致。
public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
int[] dp = new int[C + 1];
for (int i = 0; i < N; i++) {
for (int j = C; j >= v[i]; j--) {
for (int k = 0; k <= s[i] && j >= k * v[i]; k++) {
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
return dp[C];
}多重背包二进制优化
但是，多重背包有两个优化方式，来简化时间复杂度，上面的形式，在三个维度都为n级别的时候是级别的，这显然对于很多问题来说无法接受。这时候我们可以考虑的是，既然物品有k个，代表k个状态，那么我们可不可以用小于k个状态组合来表示这k个物品呢？这显然是可以的。
首先我们要知道一点点的数学基础，就是任意一个数都可以拆分成若干个的2的整数幂。也就是说我们只需要将k个物品拆分成若干个2的整数幂，并且把每一个这样的数看作是一个物品，这样我们就可以将第三层循环大大减小，在开始计算状态之前将物品数量和质量都按照2的幂次重新装在一个新的数组里就可以了。这样的优化使得多重背包问题的物品数量下降了一个数量级，将原本的s[i]个物品拆分成了logs[i]件，我们可以单秒解决的数据范围也从10^2上升到10^3。
但这并是多重背包问题优化的上限，下面的单调队列优化才是劝退我N次的罪魁祸首。
多重背包单调队列优化
单调队列
在分析这种优化之前，我们先来看看单调队列，到底是用来解决什么问题的。
考虑这样一个问题：
给出一个数组，求这个数组中每k个数中的最大值
这个问题我们显然无法简单的通过维护一个最大值遍历来完成，因为我们需要保存小于当前区间最大值的一些状态，以用于当前最值移除窗口以后更新最值。
那么这时候我们可以很自然的想到用一些数据结构，例如队列或者栈。之前在接雨水之类的问题中，我尝试过使用单调栈来解决一类寻找下一个更大数的问题。而这个寻找区间最值的问题，则需要使用单调队列来解决。单调队列在实现上，基本和单调栈完全一样，我们使用deque并且将每一个值存入时将队列尾的所有小于当前值的数弹出即可。这样我们在单调队列中保存的数一定是单调递减的，队首的值一定是区间内的最值，每当我们将一个新的数加入区间后如果这个数大于队列中的某些数，可以直接将那些数删除。因为在新加入的这个值移除区间之前，区间的最值都将会是新加入的值，并且前面比当前值更小的状态会比当前值更早移出队列，也就没有了保存这个状态的价值。当然除了加入，我们还需要每次移动区间时，判断当前区间的长度是否已经是最大值，如果是的话需要将最值也就是左端的值移出队列。
通过这样去维护一个单调队列，我们可以在任意的区间，用的时间取得最值。
多重背包的单调队列实现
然后我们来分析一下为什么多重背包问题可以用单调队列来优化。我们观察一个背包的迭代过程，
dp[j] = max(dp[j],dp[j-v]+w,dp[j-2 *v]+2*w , ..... , dp[j-s*v]+s*w) //假设j - s * v > 0)可以看到，每后一个状态都是由与之下标，对v同余的状态转移而来，例如假设背包大小为10，并且物品重量为2，数量为3时。
可以看到根据上述的例子中，dp10和dp8的状态十分相近，当两个状态对某个物品同余时，对后面状态的判定就可以转化为一个滑动窗口的最值问题。后面的状态可以通过在所有对该物品重量同余的数中间创建一个滑动窗口，然后用单调队列维护这个滑动窗口，我们就可以在的时间里取得窗口内状态的最大值。
上述的例子可以转化为下面的通式：（物品数量不限于3了）
dp[j] = dp[j]
dp[j+v] = max(dp[j] + w, dp[j+v])
dp[j+2v] = max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])
.....但显然，上述的形式虽然有明显的规律，我们可以找到对应的dp状态，但是无法很好的维护一个单调队列，因为每次迭代后，区间内的状态都会变化。
这时候我们对所有状态同时减去(k-j)/v个w的时候上述的通式会转化成下面这样：
dp[j] = dp[j]
dp[j+v] = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w
......显然，当每个等式中所有数同时减去一个值的时候，所求的最值项还是原来的最值项，我们只需要在维护队列时保存下标数据就可以在更新dp状态的时候用第一个通式的数值去更新即可。
但是上述实现还是有不少难理解的点的。
例如虽然我们维护单调队列时，如果需要判断队列尾的值是否小于当前值时，需要使用第二个通式中的项去做对比，也就是需要减去对应的w。然后队列中储存的其实是，第二个通式中最大项的下标，而我们更新dp状态的时候就需要使用这个最大项的下标再利用第一个通式中的项去更新。所以实际上第二个通式的项我们只用来比较，并且用来维护单调队列，保存下标的，而非像之前说到的单调队列问题中一样直接比较并保存数值。
其次，需要注意的是，在用单调队列的前提是，我们将这个问题的通式经过分析后转化为了通过取余对问题进行划分，从而将问题转化为了滑动窗口问题，再配合某种数据结构来解决。
在我们维护队列的过程中，要一直保持窗口的长度小于等于物品的数量，而窗口的长度，则是队列中的最值下标距离当前值下标的距离。换而言之，队列中的下标代表了背包的容量，如果最值下标的容量加上对应的物品最大重量大于我们当前的容量时，说明通过当前最值转化为当前容量所需要的物品大于我们所能提供的最大数量si，这样当然是无法通过这个值转移的，所以需要一直维护这个区间的长度为si。
((j + k * w) - (j + que[head] * w)) / w > s原式大致等于这样，当我们满足这个等式的时候说明需要从que[head]这个状态转移到k这个状态所需要的物品数量大于我们所能提供的s了。
下面是完整代码：
int backPackVII(int n, vector<int> &prices, vector<int> &weight, vector<int> &amounts) {
// write your code here
vector<int> dp(n+1);
vector<int> g(n+1);
int len = prices.size();
int front,tail;
int que[n+1];
// memset(que,0,sizeof(que));
for(int i = 0 ; i < len ; i ++){
int vi = prices[i];
int wi = weight[i];
int si = amounts[i];
//每轮交换新老数组
swap(dp,g);
for(int j = 0 ; j < vi ; j ++){
front = 0,tail = -1;
for(int k = j ; k <= n ; k += vi){
dp[k]=g[k];
//每一次都对队列中距离K最远的下标进行判断队列长度是否大于s
if(front<=tail&&k-que[front]>si*vi)front++;
//对当前的k取出队列中最大的值的下标加上对应的物品价值来更新dp
if(front<=tail)dp[k] = max(dp[k],g[que[front]]+(k-que[front])/vi*wi);
//维持队列，每次添加当前的k值时，从队列尾部将所有队列中对应的值小于对应k值的下标，全部出列
while(front<=tail&&(g[que[tail]]-(que[tail]-j)/vi*wi)<=g[k]-(k-j)/vi*wi)tail--;
que[++tail] = k;
}
}
}
return dp[n];
}到这里，多重背包问题终于算是告一段落了，这个问题里其实有不少的难以理解的点。例如如何通过取余将问题划分为区间最值问题。文章中的二进制优化本质是对物品的数量进行划分，而单调队列优化则是对状态进行划分。单调队列的使用，单调队列计算时维护的值不等于取出最值时所使用的值等等。之后可能还会去尝试多写一点取余划分的题来加深对于这个点的理解把。
参考：