多重背包 O(VN) 做法 | 单调队列 ##

---

题解

---

题目

有$n$种物品，每种物品的数量为$c[i]$。从中任选若干件放在容量为$m$的背包里，每种物品的体积为$w[i]$（为整数），与之相对应的价值为$p[i]$（为整数）。求背包能够容纳的最大价值。

Input

第1行，2个整数，$n$和$m$中间用空格隔开。$m$为物品的种类，$m$为背包的容量。(1 <= $n$ <= 100，1 <= $m$ <= 50000)
第2 - $n$ + 1行，每行3个整数，$w[i]$，$p[i]$ 和 $c[i]$ 分别是物品体积、价值和数量。(1 <= $w[i], p[i]$ <= 10000， 1 <= $c[i]$ <= 200)

Output

输出可以容纳的最大价值。

---

题解

多重背包。

首先写出朴素的状态转移方程（$dp[i][j]$表示前$i$个物品、总体积为$j$）：

$$dp[i][j] = \max_{k = 0}^{c[i]} dp[i - 1][j - k * w[i]] + k * p[i]$$

直接这样算的复杂度最差可达$O(nm^2)$（$c[i]$极大、$w[i]$极小时）。

那么我们如何优化呢？考虑$w[i]$为$x$、$j$为$4x, 5x, 6x$、$c[i]$为$2$时的计算过程：

$dp[i][4x] = max(dp[i-1][4x], dp[i-1][3x] + p[i], dp[i-1][2x] + 2p[i])$
$dp[i][5x] = max(dp[i-1][5x], dp[i-1][4x] + p[i], dp[i-1][3x] + 2p[i])$
$dp[i][6x] = max(dp[i-1][6x], dp[i-1][5x] + p[i], dp[i-1][4x] + 2p[i])$

提出一些$p[i]$，将以上三式整理一下：

$dp[i][4x] = max(dp[i-1][4x], dp[i-1][3x] + p[i], dp[i-1][2x] + 2p[i])$
$dp[i][5x] = max(dp[i-1][5x] - p[i], dp[i-1][4x], dp[i-1][3x]) + p[i]$
$dp[i][6x] = max(dp[i-1][6x] - 2p[i], dp[i-1][5x] - p[i], dp[i-1][4x]) + 2p[i]$

可以发现，以上三式的计算中有许多重复的地方。

那么如何消除重复，达到优化呢？观察原始方程：

$$dp[i][j] = \max_{k = 0}^{c[i]} dp[i - 1][j - k * w[i]] + k * p[i]$$

设$a = j \% w[i], b = j / w[i]$，则上式等价于：

$$dp[i][a + b * w[i]] = \max_{k = b - c[i]}^{b} dp[i - 1][a + k * w[i]] - k * p[i] + b * p[i]$$

那么在每个i循环中，可以把所有的j按a分成w[i]组，每组新建一个队列，枚举b，每次把$dp[i - 1][a + k * w[i]] - k * p[i]$放进队列，并保持队列长度不超过c[i]，用O(1)求出队列中最大值、从最大值转移即可。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 103, M = 50003;
int n, m, w[N], p[N], c[N], ans;
//w[i]: 体积; p[i]: 价值; c[i]: 数量
int dp[M], qa[M], qb[M], la, lb, ra, rb;
//qa: 正常队列; qb: 用来求最大值的辅助队列
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d%d%d", &w[i], &p[i], &c[i]);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < w[i]; j++){
            la = lb = 0, ra = rb = -1;//清空队列
            for(int k = 0; j + k * w[i] <= m; k++){
                if(ra - la + 1 > c[i])//如果队列中元素个数超过限制
                    if(qb[lb] == qa[la++]) lb++; //从队首弹出
                int x = dp[j + k * w[i]] - k * p[i];
                qa[++ra] = x;
                while(rb >= lb && qb[rb] < x) rb--;
                qb[++rb] = x;
                dp[j + k * w[i]] = qb[lb] + k * p[i];
                ans = max(ans, dp[j + k * w[i]]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}