多重背包问题 III

前言：本文是收录在动态规划习题集中的一个小part，但是思来想去认为这个的难度足够作为一个独立的文章，故此有了本文。

题面描述

有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sis_i 件，每件体积是 viv_i ，价值是 wiw_i 。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

原题链接：AcWing 6. 多重背包问题 III

方法：单调队列优化

复杂度：O(NV)O_{(NV)}

  1. 考虑最原始的多重背包的求解方案：

    多重背包问题（图一）

    可以看到 f[i,j]f[i,j]​ 与 f[i,j+v]f[i, j+v]​ 它们在计算推导的过程中重复计算了大量相同的项，而 f[i,j+1]f[i, j+1]​ 与 f[i,j+1+v]f[i, j+1+v]​ 也在推导的过程中计算了大量相同的项，据此我们可以根据这个特性减少计算量。

  2. 我们可以发现所有背包容量（j）对于当前物品体积（v）同余的项都在计算的过程中重复计算了大量相同的项其中相同的项之间也是同余于当前物品体积的，而背包容量与当前物品体积不同余的项之间在计算时没有相同项重复计算的情况；

    据此，我们可以将背包容量更具对当前物品体积v取模得到的余数分为v类，在每一类的计算过程中根据重复计算设计方案来减少/避免重复计算；

  3. 现在考虑第r类（所有当前背包容量j与当前物品体积v取模的余数都为r的项，即所有与r同余于当前物品体积v的j）

    多重背包问题（图二）

  4. 上图中已经说明了是用到了滑动窗口来解决问题的，下面我们来分析一下如何维护这个滑动窗口：

    首先我们很容易分析得到这个滑动窗口的大小就是当前物品的数量；

    其次我们在滑动窗口中维护的值为当前滑动窗口内的最大值，这就很容易联想到“滑动窗口内的最大值”模板题了，而这题的解法就是用到了单调队列维护滑动窗口的（不了解滑动窗口的读者可以自行阅读单调栈和单调队列）；

  5. 但是我们可以发现窗口内的数的表达式是在不断变换的，而对于“滑动窗口内的最大值”而言维护的窗口内的数值是固定不变的

    对于本题的需求而言我们显然不能单纯地将具体的值存入单调队列中；

    首先，我们考虑在滑动窗口内的数的表达式的相同点选取具有代表性的第一项 f[i−1,r]+xwf\left[i-1,r\right] + xw 在不断滑动窗口的过程中不变的是 f[i−1,r]f\left[i-1,r\right] 项，变化的只有 +xw+xw 项，而这里的 x 的值实际上就是将x 个物品装入已经装入体积为 j′j^{'} 的背包中使给背包装入的物品的总体积为当前背包容积 j，所有这里的 x 的计算公式就是 x=(j−j′)/vx = (j-j^{'})/v ；

    就此我们可以发现在滑动窗口中任意两项之间的的差距一定是f[i−1,j1]−f[i−1,j2]−(j1−j2)/v×wf[i-1, j_1]-f[i-1, j_2]-(j_1-j_2)/v\times w ，这也就意味着我们在单调队列中只需要保存 j1,j2,...,jnj_1, j_2, ..., j_n 的值即可，在维护单调队列时只需要比较 f[i−1,ji]−ji/v×wf[i-1, j_i] - j_i/v\times w​​ 的值即可。

    （理解到这里还是很重要的但好像y总和很多博文都讲得比较含糊）

  6. 思路讲解结束了，我们现在总结一下前面的分析结论：

    1. 对于每个体积为 vv 的物品，将背包容积 mm 按照同余于 vv 分为 vv 类，分别求值
    2. 当前 f[i,j]f[i, j] 的值的求法就是取大小为当前物品数量 ss 的滑动窗口内的最大值
    3. 滑动窗口由单调队列来维护，其值维护了当前背包容量 jij_i ，具体判断项的入队与弹出由 f[i−1,ji]−ji/v×wf[i-1, j_i] - j_i/v\times w 来决定

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 20010;
int n, m;
int f[N][N];
int q[N];


int main(){
    cin>>n>>m;
    
    for(int i = 1; i <= n; i++){
        int v, w, s;
        cin>>v>>w>>s;
        
        //分成r类
        for(int r = 0; r < v; r++){
            int hh = 0, tt = -1;
            for(int j = r; j <= m; j+=v){
                
                f[i][j] = f[i-1][j];
                
                //超过滑动窗口的体积
                if(hh <= tt && (j-q[hh])/v > s) hh++;
                if(hh <= tt) f[i][j] = max(f[i][j], f[i-1][q[hh]]+(j-q[hh])/v*w);
                
                //弹出旧且表达式值小于当前值的项
                while(hh <= tt && f[i-1][q[tt]]-q[tt]/v*w <= f[i-1][j]-j/v*w) tt--;
                
                q[++tt] = j;
            }
        }
    }
    
    cout<<f[n][m]<<endl;
    return 0;
}

状态压缩空间优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main(){
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        int v, w, s;
        cin>>v>>w>>s;
        memcpy(g, f, sizeof f);
        for(int j = 0; j < v; j++){
            int hh = 0,  tt = -1;
            for(int k = j; k <= m; k+=v){
                if(hh <= tt && q[hh] < k-s*v) hh++;
                if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh])/v * w);
                while(hh <= tt && g[q[tt]]-(q[tt]-j)/v * w <= g[k]-(k-j)/v * w) tt--;
                q[++tt] = k;
            }
        }
    }
    
    cout<<f[m]<<endl;
    return 0;
}

后记：有空会把二进制优化版的补充在后面滴~