使用单调队列优化的 O(nm) 多重背包算法
浏览数：23 /
时间：2015年06月08日
我搜索了一下，找到了一篇很好的博客，讲的挺详细：链接。
解析
多重背包的最原始的状态转移方程：
令 c[i] = min(num[i], j / v[i])
f[i][j] = max(f[i-1][j-k*v[i]] + k*w[i]) (1 <= k <= c[i]) 这里的 k 是指取第 i 种物品 k 件。
如果令 a = j / v[i] , b = j % v[i] 那么 j = a * v[i] + b.
这里用 k 表示的意义改变， k 表示取第 i 种物品的件数比 a 少几件。
那么 f[i][j] = max(f[i-1][b+k*v[i]] - k*w[i]) + a*w[i] (a-c[i] <= k <= a)
可以发现，f[i-1][b+k*v[i]] - k*w[i] 只与 k 有关，而这个 k 是一段连续的。我们要做的就是求出 f[i-1][b+k*v[i]] - k*w[i] 在 k 取可行区间内时的最大值。
这就可以使用单调队列优化。
代码
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
