单调队列多重背包时间复杂度O(vn)

版权声明：本文为博主原创文章，未经博主允许不得转载。

多重背包问题：

有N种物品和容量为V的背包，若第i种物品，容量为v[i]，价值为w[i]，共有n[i]件。怎样装才能使背包内的物品总价值最大？

网上关于“多重背包”的资料倒是不少，但是关于怎么实现O(N*V)算法的资料，真得好少呀，关于“单调队列”那部分算法，又没说明得很清楚，看了几遍没看懂原理，只好自己动脑去想怎么实现O(N*V)算法。

若用F[i][j]表示对容量为j的背包，处理完前i种物品后，背包内物品可达到的最大总价值，并记m[i] = min(n[i], j / v[i])。放入背包的第i种物品的数目可以是：0、1、2……，可得：

F[i][j] = max { F[i - 1] [j – k * v[i] ] + k * w[i] }  (0 <= k <= m[i])       ㈠

如何在O(1)时间内求出F[i][j]呢？

先看一个例子：取m[i] = 2, v[i] = v, w[i] = w, V > 9 * v，

并假设 f(j) = F[i - 1][j]，观察公式右边要求最大值的几项：

j = 6*v:   f(6*v)、f(5*v)+w、f(4*v)+2*w 这三个中的最大值

j = 5*v:   f(5*v)、f(4*v)+w、f(3*v)+2*w 这三个中的最大值

j = 4*v:   f(4*v)、f(3*v)+w、f(2*v)+2*w 这三个中的最大值

显然，公式㈠右边求最大值的几项随j值改变而改变，但如果将j = 6*v时，每项减去6*w，j=5*v时，每项减去5*w，j=4*v时，每项减去4*w，就得到：

j = 6*v:   f(6*v)-6*w、f(5*v)-5*w、f(4*v)-4*w 这三个中的最大值

j = 5*v:   f(5*v)-5*w、f(4*v)-4*w、f(3*v)-3*w 这三个中的最大值

j = 4*v:   f(4*v)-4*w、f(3*v)-3*w、f(2*v)-2*w 这三个中的最大值

很明显，要求最大值的那些项，有很多重复。

根据这个思路，可以对原来的公式进行如下调整：

假设d = v[i]，a = j / d，b = j % d，即 j = a * d + b，代入公式㈠，并用k替换a - k得：

F[i][j] = max { F[i - 1] [b + k * d] - k * w[i] } + a * w[i]   (a – m[i] <= k <= a)   ㈡

对F[i - 1][y] （y= b  b+d  b+2d  b+3d  b+4d  b+5d  b+6d  …  j）

F[i][j]就是求j的前面m[i] + 1个数对应的F[i - 1] [b + k * d] - k * w[i]的最大值，加上a * w[i]，如果将F[i][j]前面所有的F[i - 1][b + k * d] – k * w放入到一个队列，那么，F[i][j]就是求这个队列最大长度为m[i] + 1时，队列中元素的最大值，加上a * w[i]。因而原问题可以转化为：O(1)时间内求一个队列的最大值。

该问题可以这样解决：

① 用另一个队列B记录指定队列的最大值（或者记录最大值的地址），并通过下面两个操作保证队列B的第一个元素（或其所指向的元素）一定是指定队列的当前最大值。

② 当指定队列有元素M进入时，删除队列B中的比M小的（或队列B中所指向的元素小等于M的）所有元素，并将元素M（或其地址）存入队列B。

③ 当指定队列有元素M离开时，队列B中的第一个元素若与M相等（或队列B第一个元素的地址与M相等），则队列B的第一个元素也离队。

经过上述处理，可以保证队列B中的第一个元素（或其指向的元素）一定是所指定队列所有元素的最大值。显然队列B的元素（或其所指向的元素）是单调递减的，这应该就是《背包九讲》中的提到的“单调队列”吧，初看的时候被这个概念弄得稀里糊涂，网上的资料提到“维护队列的最大值”，刚开始还以为是维护这个单调队列的最大值，对其采用的算法，越看越糊涂。其实，只要明白用一个“辅助队列”，求另一个队列的最值，那么具体的算法，和该“辅助队列”的性质（单调变化），都很容易推导出来。

在多重背包问题中，所有要进入队列的元素个数的上限值是已知的，可以直接用一个大数组模拟队列。

“多重背包”通用模板:

多重背包特例：物品价值和体积相等（w = v）

由于w = v，上面的代码可进行如下修改：

入队的元素： tt = f[k] - (k / v) * w = f[k] - (k - j) = f[k] - k + j

    返回的最大值：*qb + (k / v) * w =  *qb + k - j

由于j是定值，可调整入队的元素为: f[k] - k，最大值为 *qb + k

但这种做法相当低效。实际上，这相当于一个“覆盖”问题：在放入前i个物品后，体积为j的背包，只存在两种状态：是否能刚好装满，也就是，是否能被覆盖。因而只要记录下该状态就可以了，前面的分析进行相应的调整：

对F[i - 1][y] （y= b  b+d  b+2d  b+3d  b+4d  b+5d  b+6d  …  j）

F[i][j]就是求j的前面m[i] + 1个数对应的F[i - 1] [b + k * d]（其值为0或1）的最大值，即j前面的m[i] + 1个0、1数据中是否存在1，这又可以简化为判断它们的和是否不等于0。

另外，可以倒着读数据，这样就不需要额外使用一个数组存放临时数据：

前面的代码，都在循环中对队列的元素个数进行判断，这可以通过下面的方法避免，将循环拆分成两部分：一部分都有入队和出队操作、另一部分只有入队（或出队）操作。

对该特例，还有一种O(N * V)解法：用一个数组记录当前物品已经使用数，关键代码：

if (! f[i] && f[i - v] && count[i - v] < n)

f[i] = true, count[i] = count[i - v] + 1;

每计算一类物品，count数组都要初始化一次，比较费时，可以再用一个数组记录上一次处理的物品编号，通过判断上一次放入那一类的物品编号与当前这类物品编号是否一致（不一致时，相当于count[i]值为0的情况），从而避免对count数组的初始化操作。还可以将初始化count数组和后面的循环整合在一起。

POJ 1742：有若干不同面值的纸币，问能组合出1到m中的几种面值？

用自己随机生成的数据测试了下，上面提到的几种方法，所用时间都是7秒多点，有排序的比没排序的稍微快点。但在POJ上提交的结果，不同代码的耗时相差挺大，快的在1秒左右，慢的接近1.5秒。

还有一种特例：

给定面值为1、2、5的纸币若干个，问其所不能支付的最低价格（假设为自然数）。

这可以用多重背包（或母函数）来解决，但实际上是有O(1)解法的。