多重背包问题（单调队列优化）

共计 1129 个字符，预计需要花费 3 分钟才能阅读完成。

题目大意

题目链接

有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$ ，求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

从朴素思考

我个人觉得先从朴素来推出我们的单调队列优化比较容易。

在朴素版本当中，我们要枚举每一种物品选择多少个，然后枚举每一种可能的状态。

for(int i = 1; i <= n ;i++){
    for(int j= 0; j<=m ;j++){
        for(int k =0 ; k <= s[i] && k * v[i] <= j ; k ++ ){
            dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
        }
    }
}

根据递推式推导

我们对单独一种物品分析，$dp[i][j]$ 可以从 $dp[i-1][j - k * v]$ 转移而来,所以我们可以得到下式。

我们由这个递推式发现这个东西和滑动窗口非常相似啊，我们要算的其实就是以 $s$ 为大小的滑动窗口中的最大值,并且可以看出 $最终体积 \% v[i]$ 相等的是一类情况，因为要算$f[j]$一定要有$f[j-v[i]],f[j-2 * v[i]] \dots f[r] (r = j \% v[i])$，也就是说必须先把这一类一起算完才行，这样我们每一类用一次单调队列就可以了，否则我们就要同时维护多个单调队列。

还有我们可以发现我们的数转移过来的时候是不能直接使用的，我们还需要加上 $k * w (k \in 1,2,3,\dots,s)$，这个 $k$ 值就是我们的$\frac{体积之差}{v[i]}$（因为我们把体积当做了下标，所以直接取单调队列队头和当前的j相减即可），这通过上面的递推式就可以看出。

还有就是这道题必须要有两维，否则就要使用滚动数组，因为我们根据递推式必须要正着遍历，但我们如果正着遍历，当我们要用到前面的数时，其已经更新了，变着你成了当前这一层，但我们想要的是上一层。

代码

int v[N], w[N], s[N] ;
int q[N] ;
int f[N], g[N] ;
void solve(){
    cin >> n >> m;
    _rep(i,1,n){
        cin >> v[i] >> w[i] >> s[i] ;
    }
    _rep(i, 1, n){
        memcpy(g,f,sizeof g) ;
        _rep(r, 0, v[i] - 1){//分类
            int hh = 0 , tt = -1 ;
            for(int j = r ; j <= m ; j += v[i]){
                if(hh <= tt && (j - q[hh]) / v[i]  >  s[i]) hh ++ ;
                while(hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j] ){//新的元素更优
                    tt -- ;
                }
                q[++tt] = j ;
                f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i] ;
            }
        }
    }
    cout << f[m] << endl ;
}