多重背包的单调队列优化

邮专学子周末早起迎寒风细雨所作............. 周末也别想休息！！！

耐心看完，必定有收获哦🥰🐯

多重背包与其他背包相比的最大区别点就是，每个物品的数量是有限的。下面我们来看看多重背包的更新特性，可以从递推公式上琢磨琢磨.......

相关参数的解释

v代表体积，w代表价值，s代表物品数量，i代表放入背包的第i件物品，g数组存放没有放入i物品前各容量背包的原始价值，其它参数根据情况而定。

单调队列

元素值不递增的队列，谓之单调队列，还没弄懂概念的同学可以去搜索相关博客进行理解

背包更新的特性

测试代码

#include<iostream>
#include<cstdio>
using namespace std;

int dp[1005];
int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1;i <= N;i++) {
        //从背后开始遍历,避免物品重放
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = V;j >= v;j--) {
            for (int k = 1;k <= s;k++) {
                if (j >= k * v) {
                    dp[j] = max(dp[j], dp[j - k * v] + k * w);
                    printf("dp[%d] = %d dp[%d] = dp[%d] + %d*%d
", j, dp[j], j, j - k * v, k, w);
                }
                else {
                    break;
                }
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

递推公式：dp[j] = max(dp[j], dp[j - k * v] + k * w)

很显然，背包dp[j]的最大值是由其自身得到，或者是从容量与其相差k*v的背包更新而来。姑且认定容量之间相差k*v的背包为一类，那么对于放入体积为v的物品，背包更新的种类就可以分为起始容量为0,1,2......v-1种，比如dp[0],dp[0+v],dp[0+2v]......dp[0+k*v]......

从此处开始，参数的含义与测试代码不同。

j表示同类背包的起始容量,k表示待更新最大值的背包容量,t表示物品相差个数。

很显然，背包只能在同类间更新，且被更新背包的容量较大,倘若能够一次性选取到dp[k-t*v]+t*w最大的背包maxBag(定义名词)，该背包的容量为k-t*v，那么背包dp[k]的最大值只需要更新一次，时间复杂度为O(1)。为了简化问题的讨论，我们姑且认为dp[k]就是从同类背包dp[k-t*v]的基础上更新而来，下面讨论如何遍历特点与选取价值最大的容量背包maxBag。

遍历特点

由于背包在同类间更新，而且较大容量背包的最大价值是由较小背包的最大价值推导而来，因此遍历背包的顺序是从小容量到大容量。然而，这种更新方式会使物品重复放入，因而需要用一个辅助数组g来存放在没有放入第i件物品之前，各个容量背包的最大价值。那么递推公式应该为:

dp[k] = max(g[k],g[k-t*v]+t*v)

如何选取maxBag

(j代表同类背包的起始容量，牢记参数含义)

给出存放规则如下：倘如g[k2] - (k2 - j)/v*w >=g[k1] - (k1 - j)/v*w ，那么

由于i物品的数量s有限，故dp[k]背包所借助的maxBag，其容量vv,必须满足如下关系式: ；因此，由于maxBag的使用受到物品个数影响，故当maxBag1不能再被使用时，需要借助maxBag2，也就是说，我们需要借助一个队列来存放此类背包{maxBag1,maxBag2......maxBag(n)},倘若待更新背包的容量k满足：，那么maxBag1更新最大容量，否则maxBag1退出队列，借助maxBag2更新dp[k]的最大价值。

因而，我们需要借助 int q[maxn]来存放maxBag,队头的下标为hh,队尾的下标为tt,q[x]代表maxBag的背包容量，下面给出maxBag的入队规则，假如 g[k1] - (k1-j)/v*w >= g[k2] - (k2 - j)/v*w,那么容量为k1的背包必定排在容量为k2的背包前面，这是因为当我们分别讨论dp[k]借助g[k1],g[k2]更新最大价值时(依旧先前规定，不讨论dp[k]借助自身更新最大值)：

dp[k] = g[k1] + (k-k1)/v*w >= dp[k] = g[k2] + (k - k2)/v*w，该不等式很容易证明。

总而言之，倘若q[hh]代表队头背包的容量，因而 当(k-q[hh])>s*v时，hh++,当dp[k]结束更新后需要考虑将其加入队列,dp[k]的更新公式如下:

dp[k] = max(g[k], g[q[hh]] + (k - q[hh]) / v * w)

代码实现

语言:C++ 环境:VS2022

（可以用于通过AcWing困难级别的多重背包问题）

#include<iostream>
#include<cstdio>
using namespace std;

const int maxv = 20005;
const int maxn = 1005;
int dp[maxv];
int g[maxv];

int main() {
    int N, V;
    cin >> N >> V;
    //确保容量的最大值不超过maxv
    if (V >= maxv) {
        return 0;
    }
    //依次放入N件物品
    for (int i = 1;i <= N;i++) {
        int v, s, w;
        cin >> v >> w >> s;
        //将v分类,g表示在放入i物品之前的各容量背包的价值状态
        memcpy(g, dp, sizeof dp);
        for (int j = 0;j < v;j++) {
            //讨论容量为k的背包的更新,hh表示队头，tt表示队尾
            //q[hh]存放最大净值背包的容量    
            int hh = 0, tt = -1;
            int q[maxv] = { 0 };
            for (int k = j;k <= V;k += v) {
                //如果队列的长度大于物品的个数，那么需要更新队头
                if (hh <= tt && (k - q[hh]) > s * v)  
                    hh++;
                //更新最大容量
                if (hh <= tt)  
                    dp[k] = max(g[k], g[q[hh]] + (k - q[hh]) / v * w);
                //将dp[k]
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
                    tt--;
                q[++tt] = k;
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

算法的时间复杂度

由于每当加入一个物品时，各个容量的背包只需要更新一次，因此倘若不包括队列的更新，则时间复杂度为O(NV),N代表物品个数，V代表背包最大容量。再讨论最内层的队列更新循环，由于队列最大长度不超过物品的个数s，故更新最好的情况为O(1),最坏情况为O(s),故总体时间复杂度的范围是:O(NV)~O(NVs),由于s是一个变量，而且相对于NV而言比较小，姑且认为时间复杂度为O(NV).相比如朴素算法的O()已经提升一大截了。

结语

队列优化多重背包算法涉及将背包本身按照容量分类的思想（二进制优化是将物品个数分类），需要理解其分类思想，背包更新的特性以及如何利用单调队列更新最大价值.......

思路有点复杂，一遍看不懂不要灰心，多去看看别人的博客，多看看相关视频，多敲几遍代码自己体会，很快就会有头绪了（本人也是花了一整天时间才了解了一点点）。最后希望同学们若真的理解了，将自己的理解分享出去，这样会进一步加深对该算法的理解呢。

结束！！！