下面，我们来一点一点推导单调优化的过程。首先，我们假设当前遍历到的状态是i，也就是背包容量是i，当前的物品是item，它的体积是v，价值是p，数量是n。我们先来看第一个洞见，对于状态i而言，它只能从i-kv状态转移得到。这里的k是一个[0, min(i / v, n)]范围内的整数，min(i / v, n)这个式子我想应该大家都能看懂，就是当前状态i最多能够包含多少个物品item。这个数量是物品数量的上限n和i这个状态最多装得下的数量i / v中较小的那个，我们令min(i / v, n)这个值叫做cnt。也就是说对于状态i而言，它最多包含cnt个item，最少包含0个。那么它的转移可能性一共只有cnt种，而不可能从i-1以及i-2等其他状态转移到。我们写出这个状态转移方程，可以得到：也就是说在当前item也就是当前决策下，状态i的最好结果一定是由一系列确定的子状态其中之一转移得到的，并且这些子状态和一个整数k挂钩，k的取值范围是[0, cnt]。我们先暂时忽略这个范围，简化问题。考虑最极端的情况，最极端的情况这个物品数量管够，在这种情况下，我们可以列一下可以通过item转移到i的所有状态，它是一个序列：[i % v, i % v + v, i % v + 2v, ..., i - v]。在之前裸的做法当中，我们是通过一重循环来遍历了这个序列，从其中找到了最佳的转移。我们现在希望可以不用遍历，通过某种方法快速找到其中最优的状态进行转移。这个逻辑应该不难理解，到这里，我们没有引入任何花哨的操作。我们下面来做一点简单的分析，我们已经列举出了对于状态i所有可能转移到的上游状态。我们不希望通过遍历来找到其中最佳的转移，顺着这个思路，我们大概可以猜测一下，应该通过某种方法找到这个序列当中的某个最值。只有这样，我们才可以不需要遍历，快速找到答案。但是通过什么方法，寻找什么最值我们现在还不知道。到这里，我们又往前进了一步，大概知道了接下来的策略，但是具体的细节我们还不知道，没关系，我们先放一放，继续进行分析。为了简化书写，我们令 m = i % v，也就是当前状态对物品item体积的余数。那么上面的那个序列可以写成[m, m+v, m+2v, ... i - v]。由于在本问题当中，我们希望背包里的价值越大越好，所以显然对于dp[m], dp[m+v], dp[m+2v]... 这个序列而言，它是递增的。原因也很简单，对于每一个状态而言，dp数组当中都存储的它对应的最优结果。所以不可能出现我们用了更多的空间，但是背包里的价值却减少的情况。我们当然希望可以简单地从dp[m], dp[m+v], dp[m+2v]...dp[i-v]这个序列当中选取最大的那个，但是由于上面这个结论，所以我们并不能这么做。不能这么做的原因有两个，一个刚才说了，因为dp[i]是一个随着i递增而递增的序列，背包装的东西越多，装的价值只会越大，不会减少。还有一个原因是后效性，这个问题和零一背包的情况有些相似。举个例子，比如说dp[m] = x，如果dp[m+v]=x+p，也就是说dp[m+v]由dp[m]转移得到，代表它已经装了一个物品item。如果我们再从dp[m+v]进行转移，我们则无法判断到底一共拿取了多少个物品，也就无法判断是否违法。这两个问题，我们一个一个来解决，先说第二个问题。这个问题解决的方法很多，最简单的就是将这个序列的结果单独存储一份，使得当我们更新dp的时候不会影响。在零一背包当中我们通过倒叙遍历来解决了这个问题，但是在多重背包当中，这种方法不太适用。接着我们来看第一个问题，我们直接找到序列最值不可行的原因是因为背包容量引起了不公，为了解决问题，我们需要想办法消除这种不公。消除的办法也简单，我们可以通过某种方法，将这些值放到同一个基准，消除因为容量变化引起的不公。实际上这个基准很好找，就是m。我们假设dp[m], dp[m+v], dp[m+2v]...dp[i-v]这个序列当中的值都是通过dp[m]转移得到的。比如dp[m+v]，如果是从dp[m]转移得到的，那么dp[m+v]应该等于dp[m]+p。同理，dp[m+2v]应该等于dp[m]+2p。这里需要注意，这里的数据都是没有经过item物品更新过的结果，是上一个物品更新之后得到的值。所以这里的dp[m+v]一定不是通过dp[m]转移得到的，如果dp[m+v] - p > dp[m]，那么显然可以说明dp[m+v]的潜力要比dp[m]更大，因为同样的体积v，它创造了更多价值。同理，如果dp[m+2v] - 2p > dp[m+v] - p，则说明dp[m+2v]的价值更大。以此类推， 我们可以得到一个全新的序列：[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]这个时候，我们已经消除了背包容量变化带来的偏差，我们可以放心地从其中选择最值作为最佳的状态转移了。但是还有一个小问题，有可能最值是不成立的，举个例子，如果说我们发现dp[m+2v] - 2p的值是最大的，但是由于item这个物品最多获取cnt个，如果从m+2v这个状态转移到i，需要的数量超过cnt，那么这也是一个无效的转移。我们需要抛开它，继续往下查找次优的结果。对于区间内最值的维护，单调队列非常合适，我们可以保证队首的元素是最优的，如果队首的元素不合法，那么我们可以很方便地弹出获取次优解。也就是说我们通过单调队列维护了[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]这个区间的最值，这也是单调队列最常用的场景。
算法流程
我们整理一下上面的思路，可以整理出整个算法运行的流程。首先我们需要一重循环来遍历物品，这个是肯定跑不了的。无论用什么算法用什么优化，我们都需要遍历物品，物品是决策的基础。在01背包和二进制表示法当中，第二重循环就是直接遍历背包容量了。但是显然，在当前算法当中，我们不能这么做。因为前文当中说到，我们需要用单调队列来维护[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]这样一个序列，所以我们需要按照这个序列的顺序来遍历背包容量。我们关注到起始状态是dp[m]，这个m代表分组，也就是物品体积的余数。举个例子，如果物品i的体积是5，那么m有0，1，2，3，4这5种取值，其实这也是5的余数。相当于我们通过余数将背包容量进行分组，这样我们维护不同分组下的序列。这些分组拼装在一起就是整个背包容量。下面我们来看下代码，结合上面的叙述会更直观一些：
if __name__ == '__main__': volume = 20 dp = [0for _ in range(volume+1)] # 单调队列 deq = deque() for item in items: cnt, v, p = item for i in range(v): # 每个i代表一组新的序列 # 所以队列需要清空重新开始 deq.clear() m = (volume - i) // v for j in range(m+1): val = dp[j * v + i] - j * p while len(deq) > 0and val >= deq[-1][0]: deq.pop() deq.append((val, j)) if deq[0][1] < j - cnt: deq.popleft() dp[j * v + i] = deq[0][0] + j * p print(dp[20])
