单调队列优化多重背包模板题

朴素版的多重背包问题： AcWing 4. 多重背包问题

回顾

一共 n 类物品，背包的容量是 m

每类物品的体积为v, 价值为w，个数为s

朴素版的多重背包求解

dp[i][j] 表示将前 i 种物品放入容量为 j 的背包中所得到的最大价值
dp[i][j] = max(不放入物品 i，放入1个物品 i，放入2个物品 i, ... , 放入k个物品 i)
这里 k 要满足：k <= s, j - k * v >= 0

不放物品  i = dp[i-1][j]
放k个物品 i = dp[i-1][j - k * v] + k * w 

最终的状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2 * v] + 2 * w, ... ,dp[i-1][j - k * v] + k * w)

优化过程

实际上我们并不需要二维的dp数组，适当的调整循环条件，我们可以重复利用dp数组来保存上一轮的信息

我们令 dp[j] 表示容量为j的情况下，获得的最大价值

那么，针对每一类物品i ，我们都更新一下 dp[m] --> dp[0] 的值，最后 dp[m] 就是一个全局最优值

dp[m] = max(dp[m], dp[m-v] + w, dp[m-2 * v] + 2 * w, dp[m-3 * v] + 3 * w, ... ,dp[m-k * v] + k * w)

接下来，我们把 dp[0] --> dp[m] 写成下面这种形式（0-j表示背包放满之后剩余的容积）
dp[0], dp[v],   dp[2 * v],   dp[3 * v],   ... , dp[k * v]
dp[1], dp[v+1], dp[2 * v+1], dp[3 * v+1], ... , dp[k * v+1]
dp[2], dp[v+2], dp[2 * v+2], dp[3 * v+2], ... , dp[k * v+2]
...
dp[j], dp[v+j], dp[2 * v+j], dp[3 * v+j], ... , dp[k * v+j]

其中dp[j]的j就是 m - k * v = j,那么dp[j]就表示原方程的dp[m-k * v]
dp[v + j]就表示原方程的dp[m - (k - 1)v] 、 dp[k * v + j]就表示原方程的dp[m]
其中用最后一条dp[j], dp[v+j], dp[2 * v+j], dp[3 * v+j], ... , dp[k * v+j]就可以表示原转移方程

显而易见，m 一定等于 k * v + j，其中  0 <= j < v
所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的
也就是说，dp[k * v+j] 只依赖于 { dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] }

因为我们需要的是{ dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] }中的最大值，
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了j个单调队列的问题

所以，我们可以得到
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[j+kv] = max(dp[j] + kw,  dp[j+v] + (k-1)w, dp[j+2v] + (k-2)w , ... ,dp[j+kv])

其中这些方程都与原状态转移方程一一对应:

例如：

**转换过后：**
dp[j+kv] = max( dp[j] + kw,       dp[j+v] + (k-1)w,       dp[j+2v] + (k-2)w , ... ,dp[j+kv]) 
**原方程：**       👇                    👇                      👇                   👇
 dp[m]   = max(dp[m-kv] + kw ,  dp[m-(k-1)v + (k-1)w , dp[m-(k-2)v] + (k-2)w , ... , dp[m])

但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换

**原始**：
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[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[j + kv] - kw   **

单调队列计算每个dp[j+kv]【dp[m]】的最大值：

即max(dp[j] + kw, dp[j+v] + (k-1)w, dp[j+2v] + (k-2)w , ... ,dp[j+kv])

单调队列模板参考 AcWing 154. 滑动窗口

每件物品对应的滑动窗口：

 //判断队头元素是否还在窗口内【与窗口的最右端进行比较】（窗口的长度为当前物品的件数S）
if(hh <= tt && q[hh] < j - s * v) hh++;

详细注释版

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20010;
int f[N],g[N];  //g[]当作是第i - 1层的f[i]
int q[N]; //单调队列，里面记录的是使用的体积
int n,m;
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;++i){ //枚举n种物品

        int v,w,s;  //分别表示第i件物品的体积、价值和数量

        cin >> v >> w >> s;

        memcpy(g, f, sizeof f); //用g[]记录f[]的上一个状态

        for(int r = 0;r < v;++r){  //枚举背包的余数（最大的余数不能超过v）

            int hh = 0,tt = -1; //hh表示队头，tt表示队尾

            for(int j = r;j <= m;j+= v){  //枚举背包的体积，用单调队列计算出dp[j]的最值

                //判断队头元素是否还在窗口内【与窗口的最右端进行比较】（窗口的长度为当前物品的件数S）
                if(hh <= tt && q[hh] < j - s * v) hh++;

                //如果队尾体积对应的最大价值小于当前体积对应的最大价值，那么队尾就pop出去（单调递减队列）
                //(q[tt] - r) / v * w ：(背包体积 - 背包余积) / 单件重量 * 单件价值
               while (hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[j] - (j - r) / v * w) tt -- ;


                //当前元素入队
                q[++tt] = j;


                //更新f[j]的最大值 (队列的队头的体积所对应的就是最大的体积)
                //q[hh]就是当前要使用的背包体积
                if(hh <= tt) f[j] = g[q[hh]] + (j - q[hh]) / v * w; 
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}