多重背包单调队列优化的完整数学推导

​【多重背包单调队列优化的完整数学推导】
在多重背包问题中，单调队列优化的核心思想是将所有背包容量状态 j∈[0,V] 按当前物品的体积 vᵢ 取余分组，使状态转移严格限制在同一 “同余类” 内，进而利用滑动窗口最大值的性质，通过单调队列高效维护最优决策。多重背包单调队列优化，如同将一条笔直的主干道，按固定的间隔划分出 vᵢ 条互不干扰的独立通道。

0. 原始多重背包状态转移
设当前处理第 i 种物品，其体积为 vᵢ，价值为 wᵢ，数量上限为sᵢ。对于任意背包容量 j，原始多重背包状态转移仅依赖于以下形式的状态：f[j]=max{f[j−k·vᵢ]+k·wᵢ}，0≤k≤min(sᵢ, ⌊ j/vᵢ⌋)
其中，f[j] 表示容量为 j 时的最大价值。
原始多重背包采用上述状态转移方程，其时间复杂度高达 O(N·V·S)。在数据规模较大（0<N≤1000，0<V≤2000，0<vi,wi,si≤2000）时往往会直接导致超时（TLE），因此必须进行进一步优化。

1. 按当前物品体积分组（数学定义）
对当前物品 i，将背包容量 j 按 vᵢ 取余分组：j=r+t·vᵢ
其中：
r=j mod vᵢ，→ 余数（通道编号）
r=0, 1, 2, …, vᵢ−1 → 共 vᵢ 条独立通道
t → 组内下标（步数）

2. 状态改写（同一条通道内）
对固定余数 r，容量可表示为：j=r+t·vᵢ，其中 r=0, 1, 2, …, vᵢ−1。
代入原始状态转移方程 f[j]=max{f[j−k·vᵢ]+k·wᵢ}，0≤k≤min(sᵢ, ⌊ j/vᵢ⌋)，
得：f[r+t·vᵢ]=max{f[r+(t−k)vᵢ]+k·wᵢ}，k=0, 1, ..., sᵢ
然后，令 d=t−k，则 k=t−d，代入得：f[r+t·vᵢ]=max{f[r+d·vᵢ]−d·wᵢ}+t·wᵢ，d∈[t−sᵢ, t]

3. 最终滑动窗口形式（核心公式）
对每一条通道 r，定义 g(t)=f[r+t·vᵢ]−t·wᵢ
则上文所得状态转移方程 f[r+t·vᵢ]=max{f[r+d·vᵢ]−d·wᵢ}+t·wᵢ，d∈[t−sᵢ, t]，
变形为 f[r+t·vᵢ]=max{g(d)}+t·wᵢ，d∈[t−sᵢ, t]

4. 结论
每组内部等价于一个长度为 d=t-(t-sᵢ)+1=sᵢ+1 的滑动窗口最大值问题，可使用单调队列 O(1) 获取最大值。

【算法应用：https://blog.csdn.net/hnjzsyjyj/article/details/159202029】

#include <bits/stdc++.h>
using namespace std;
 
const int N=2e4+5;
int f[N],pre[N];
int q[N],hh,tt;
 
int main() {
    int n,V;
    cin>>n>>V;
    for(int i=0; i<n; i++) {
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(pre,f,sizeof f); //copy f to pre
        for(int r=0; r<v; r++) { //Enumerate remainders
            hh=0,tt=-1;
            for(int k=0; r+k*v<=V; k++) {
                int j=r+k*v;
                while(hh<=tt && q[hh]<k-s) hh++;
                int val=pre[j]-k*w;
                while (hh<=tt && pre[q[tt]*v+r]-q[tt]*w<=val) tt--;
                q[++tt]=k;
 
                f[j]=max(f[j],pre[q[hh]*v+r]+(k-q[hh])*w);
            }
        }
    }
    cout<<f[V]<<endl;
    return 0;
}
 
/*
in:
4 5
1 2 3
2 4 1
3 4 3
4 5 2

out:
10
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/159202029

​