历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 6. 多重背包问题 III【单调队列优化+图示】原题链接困难

作者：

一只野生彩色铅笔 , 2021-06-16 20:50:51 , 所有人可见 , 阅读 20146

502

252

最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

有 $n(0\lt n \le 1000)$ 种物品和一个容量为 $V(0\lt V \le 20000)$ 的背包

第 $i$ 种物品最多有 $s_i(0\lt s_i \le 20000)$ 件，每件体积是 $v_i(0\lt v_i \le 20000)$，价值是 $w_i(0\lt w_i \le 20000)$

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

多重背包—单调队列优化

对于 多重背包 分析，以及 二进制优化 这里不做额外讲解，直接分析 单调队列 优化方式

关于 多重背包【朴素版】 可以看这篇博客

多重背包的原始状态转移方程

$$ f(i,j) = \max\big(f(i-1,j), f(i-1,j-v)+w, \cdots, f(i-1,j-sv)+sw\big) $$

考虑用完全背包的优化方式来优化这个方程

$$ f(i,j-v) = \max\big(f(i-1,j-v), f(i-1,j-2v)+w, \cdots, f(i-1,j-(s+1)v)+(s)w\big) $$

写出这个公式好像并不是那么管用

因为 完全背包 是一口气把所有体积全部用掉，即
$$ \max(a,b,c,d) = \max\big(a,\max(b,c,d)\big) $$

然而 多重背包 对于每个物品的个数是有限制的，导致我们最终的等式是如下样子：
$$ \max(a,b,c,d) \ne \max\big(a,\max(b,c,d,e)\big) $$

但是，我们可以把这个式子继续推导下去，直到背包体积被用到不能再用为止
$$ \begin{cases} f(i,j) = \max\big(f(i-1,j), f(i-1,j-v)+w, \cdots, f(i-1,j-sv)+sw\big) \\\ \\\ f(i,j-v) = \max\big(f(i-1,j-v), f(i-1,j-2v)+w, \cdots, f(i-1,j-(s+1)v)+sw\big) \\\ \\\ f(i,j-2v) = \max\big(f(i-1,j-2v), f(i-1,j-3v)+w, \cdots, f(i-1,j-(s+2)v)+sw\big) \\\ \\\ \cdots \\\ \\\ f(i,r+sv) = \max\big(f(i-1,r+sv), f(i-1,r+(s-1)v)+w, \cdots, f(i-1,r)+sw\big) \\\ \\\ f(i,r+(s-1)v) = \max\big(f(i-1,r+(s-1)v), \cdots, f(i-1,r)+(s-1)w\big) \\\ \\\ \cdots \\\ \\\ f(i,r+2v) = \max\big(f(i-1,r+2v), f(i-1,r+v)+w, f(i-1,r)+2w\big)\\\ \\\ f(i,r+v) = \max\big(f(i-1,r+v), f(i-1,r)+w\big)\\\ \\\ f(i,r) = f(i-1,r)\\\ \\\ \end{cases} $$

其中 $r = j \mod v_i$，也可以理解为 完全背包 下把当前物品 选到不能再选 后，剩下的余数

得到 $f(i,r) = f(i-1,r)$ 后，我们再利用 完全背包优化思路 往回倒推一遍

会惊奇的发现一个 滑动窗口求最大值 的模型，具体如下：

为了方便大家观察，我们把 $f(i-1,j)$ 改写成 $f_j$

$$ \begin{cases} f(i,r) = f_r\\\ \\\ f(i,r+v) = \max\bigg(f_{r+v}, f_r+w\bigg)\\\ \\\ f(i,r+2v) = \max\bigg(f_{r+2v}, f_{r+v}+w, f_{r}+2w\bigg)\\\ \\\ \cdots \\\ \\\ f(i,r+(s-1)v) = \max\bigg(f_{r+(s-1)v},f_{r+(s-2)v}+w, \cdots, f_r+(s-1)w\bigg) \\\ \\\ f(i,r+sv) = \max\bigg(f_{r+sv}, f_{r+(s-1)v}+w, \cdots, f_r+sw\bigg) \quad (滑动窗口已满)\\\ \\\ f(i,r+(s+1)v) = \max\bigg(f_{r+(s+1)v}, f_{r+sv}+w, \cdots, f_{r+v}+sw\bigg) \quad (滑动窗口已满)\\\ \\\ \cdots \\\ \\\ f(i,j-2v) = \max\bigg(f_{j-2v}, f_{j-3v}+w, \cdots, f_{j-(s+2)v}+sw\bigg) \quad (滑动窗口已满) \\\ \\\ f(i,j-v) = \max\bigg(f_{j-v}, f_{j-2v}+w, \cdots, f_{j-(s+1)v}+sw\big) \quad (滑动窗口已满) \\\ \\\ f(i,j) = \max\bigg(f_j, f_{j-v}+w, \cdots, f_{j-sv}+sw\big) \quad (滑动窗口已满) \\\ \\\ \end{cases} $$

可能看上去还是有点复杂，为了再方便大家观察，我们去掉 $w$，然后把数组展开成一条链

具体如下图：

备注 2020年7月25日.png

于是通过该 滑动窗口 ，我们就能在线性的时间里求出 i 阶段里，所有满足 $j \equiv r \mod (v)$ 的 $f(i,j)$

滑动窗口 求 最大值 的实现，只需利用队列在队头维护一个 最大值 的 单调递减 的 单调队列 即可

为了更新所有 i 阶段里的状态 $f(i,j)$ ，我们只需再额外枚举所有的余数 $r$ 即可

不要忘记，滑动窗口内部比较最大值的时候，有一个在之前为了方便观察，被我删掉的偏移量 w

要记得加上再比较

具体就是 当前下标 和该 最大值的下标 之间差了 $x$ 个 $v$，那么就要加上 $x$ 个 $w$

在上面公式里，还是比较容易看出的吧，就不做额外的推导了

Code（二维朴素版）

写这个代码是为了方便大家理解

时间复杂度：$O(n \times v)$

空间复杂度：$O(n \times v)$

滑动窗口的长度为 $s_i+1$

#include <iostream>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[N][M];
int q[M];

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

Code（一维优化）

时间复杂度：$O(n \times v)$

空间复杂度：$O(v)$

和 01背包 的优化类似，观察到 状态转移方程，对于 i 阶段，只会用到 i-1 层的状态

因此可以采用 拷贝数组 或 滚动数组 的写法

拷贝数组写法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[M], g[M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        memcpy(g, f, sizeof g);
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[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;
    return 0;
}

滚动数组写法

#include <iostream>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];

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

123 评论

acwing_go 2023-07-08 11:34

贴一个我的理解：

/*

    时间复杂度的分析，我觉得通过代码很难看出来，
    可以通过它的计算过程以及它计算的大体次数来体会。


    比如总体积为V = 10,某个物品对应v=3
    以一个物品为例，我们计算的时候，是把这个物品按照对v取余的结果来分类的。

    v' = 0是一类，这一类有 0, 3, 6, 9      (v'表示当前正在求的体积)
    v' = 1是一类，这一类有 1, 4, 7, 10
    v' = 2是一类，这一类有 2, 5, 8

    我们通过单调队列优化，只是在每一类中进行优化(滑动窗口求最值)
    对于每个物品，我们都会求一遍v' = 0 ~ v' = 10，只是再求的过程中把它们分类了

    一共n个物品，我们会对 物品1 求一遍  v' = 0 ~ v' = 10
                       对 物品2 求一遍  v' = 0 ~ v' = 10
                       ....
                       对 物品n 求一遍  v' = 0 ~ v' = 10

    总共实际求了 n * (v'的最大值)， 即 n*m次
    所以时间复杂度是O(n*m)的

*/

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20020;

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

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 0;i < n;i ++){
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        memcpy(g, f, sizeof f);

        for(int c = 0;c < v;c ++){ // 遍历余数

            int hh = 0, tt = -1;
            for(int j = c;j <= m;j += v){ // 遍历余数为c这一类的 体积

                // 当前层的f[j]  暂时等于 上一层的g[j]  相当于 f[i][j] = f[i-1][j];  也就是s = 0情况
                f[j] = g[j]; 

                // 这里一共有s+1个元素,s=0也算一个，所以这里不是j - s*v + 1
                if(hh <= tt && j - s*v > q[hh]) hh ++; // 队列存的是下标，也是体积 

                // 队列中最大的(s!=0的其中一个)  和 s=0的进行比较
                if(hh <= tt) f[j] = max(f[j], g[q[hh]] + (j-q[hh])/v*w); 

                // q[tt]这个体积下的价值，再加上与j体积相差的体积数的价值，才能与g[j]进行对等比较   
                while(hh <= tt && g[q[tt]] + (j - q[tt])/v*w <= g[j]) tt --; 

                q[++ tt] = j;
            }
        }
    }

    cout << f[m] << endl;

}

_Agony 3个月前

我了神威难藏泪

Shine_Cai 3个月前

也没有均摊复杂度啥的，看出来还是没啥问题吧？

disheng 2022-10-28 19:29

while(head <= tail && f[i-1][q[tail]]+(j-q[tail])/v[i]*w[i] <= f[i-1][j]) tail --;是为了保证单调队列严格单调下降(队头为最大值)，
f[i-1][q[tail]]是刚才的队尾(当前其实已经是j，但j还未加进去，现在正在保证队列单调性),
(j-q[tail])/v[i]是统计队尾和j之间差了k个数，乘w[i]是因为实际上队尾和j之间还差了k个w[i]

Liang_9 2022-12-04 17:22

这是我看到最清晰的一版了，tql！！

为光nixiaK 2021-10-03 22:26

学长你好，请问为什么要枚举余数r呢？r不应该是定值么？

一只野生彩色铅笔 2021-10-03 23:23

枚举 $r$ 的意思是枚举要更新的 $r$

这里是把同一个阶段 $i$ 的所有状态 $j$ 根据模 $v_i$ 进行分类

对于同余的一类，再用 单调队列优化 更新

nope_ck 2022-05-05 19:40

一开始的j知识随机一个数

Chen_acwing_1024 2023-03-22 16:07

这里我也感觉好神奇，哈哈，不太明白

Chen_acwing_1024 2023-03-23 20:45 回复了 nope_ck 的评论

同学，您好，请问一开始的j只是随机一个数怎么理解呢，比如我求f[12],最后一个物品体积是3,那么我只需要从f[0],f[3],f[6],f[9]这几个里面取就行啊，不用知道f[1],f[2]，这些啊，感觉不需要枚举r吧

nope_ck 2023-03-23 22:42 回复了 Chen_acwing_1024 的评论

但是你想想并不是每一组物品的体积和价值是一样的哦

Noki1314 2023-03-26 15:40 回复了 Chen_acwing_1024 的评论

因为，实际上我们是要对当前$i$下所有的 $j$ 求$f(i,j)$的值，如果不遍历所有的$r$的话，不能够把所有的$j$包含在内。换个角度看，这明明是三个循环，为啥是$O(N*V)$的时间复杂度，不就是因为这个代码内部两重循环实际上就是以不同的方式遍历了一遍$j$吗。

Chen_acwing_1024 2023-03-26 16:12 回复了 Noki1314 的评论

哦哦，好的，谢谢，哈哈，我前两天看明白了，其实就是对于每个新加的物品来说都要更新从f[0]到f[m],然后遍历所有余数才能够确定每一层的f[0]到f[m]都被更新了，哈哈，这道题看了好几天，才慢慢明白

Noki1314 2023-03-26 16:15 回复了 Chen_acwing_1024 的评论

我也是hhhhhh，断断续续看了好几天了，才一点点理解，太难了（泪目

雨花斋 2023-10-04 14:03 回复了 Chen_acwing_1024 的评论

确实确实，通透

SpongeBob_ 2023-02-10 01:25

$\bf \Huge{orz}$

行_49 6个月前

楼主的图对于理解滑动窗口以及序列的选择太友好了，不过队尾元素为什么要出栈，以及这样做对于求背包最大价值的必要性没有说明清楚，这里贴一个我的理解。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20100;

int dp[2][M], q[M];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;

        // 单调队列优化动态规划
        for (int j = 0; j < v; ++j) {
            int head = 0, tail = -1;  // 对每一条序列，队列都会进行重置
            for (int k = j; k  <= m; k += v) {
                // 计算当前背包的体积为k

                // 假如队列窗口已满，则队首出列
                if (head <= tail && k- s*v > q[head])
                    ++head;

                // 维护单调队列，确保队列中元素对应的状态价值是单调递减的
                // 背包价值最大需要保持队列中物品的价值体积比(w/v)最大，而s*v决定了更新的范围。
                // 计算体积为j时对应的价值dp[j]（也就是序列的第一个元素），
                // 其实取队首元素也是可以的，都囊括了更新范围。
                // 当前体积k相比体积j价值增加的部分为(k - j) / v * w，
                // 如果用dp[k]来更新dp[j]，则dp[j]= dp[k] - (k - j) / v * w。
                // 队尾体积q[tail]（按照当前物品的价值体积比）价值增加
                // 的部分为(q[tail] - j)/v * w，如果用
                // dp[g[tail]更新dp[j],则dp[j] = dp[q[tail]] - (q[tail] - j)/v * w
                // 如果队尾计算得到的价值不大于当前，说明当前的价值体积比更优或等同，则队尾出列。
                while (head <= tail && dp[i % 2][q[tail]] - (q[tail] - j)/v * w <= dp[i % 2][k] - (k - j) / v * w)
                    --tail;

                // 将当前背包容量加入到队尾
                q[++tail] = k;

                // 现在可以保证基于头部体积q[head]可以计算出最高的当前价值
                // 更新当前背包容量对应的状态价值
                dp[(i + 1) % 2][k] = dp[i % 2][q[head]] + (k - q[head])/v * w;


            }
        }
    }
    cout << dp[n % 2][m] << endl;
    return 0;
}

MGNisme 2023-10-10 16:13

tql

崴川邱库 2023-04-13 22:16

ORZ 终于看懂了

xjsc01 2022-12-18 17:24

orz

acwing_xyy 2022-08-22 11:43

tql

jaylan 1个月前

$\huge{\color{purple}{orz}}$

WZRYWZWY 4个月前

max(a,b,c,d)≠max(a,max(b,c,d,e))

是不是写错了，联系上下文我觉得应该是

max(a,b,c,d)≠max(a,max(b,c,d))

吧（？）

Touper 5个月前

orz

Touper 5个月前

看你的题解终于悟了

四川中国人 24天前

时间复杂度不算0(nv log vm)吗？

wswsnssn 6个月前

orz ,tql！！！

i_17 7个月前

/*
#include [HTML_REMOVED]

using namespace std;

const int N = 2e4 + 10;

int n,m;

int f[N][N],v[N],w[N],s[N];
int q[N];

int main(){
cin >> n >> m;
for(int i = 1; i <= n;i ++ )cin >> v[i] >> w[i] >> s[i];

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

}
*/
#include [HTML_REMOVED]

using namespace std;

int n,m;

const int N = 2e4+ 10;

int v[N],s[N],w[N];

int f[N][N];
int q[N];
int main(){
cin >> n >> m;
for(int i =1;i <= n; i ++)cin >> v[i] >> w[i] >> s[i];

for(int i = 1;i <= n ;i ++ ){

    for(int j = 0; j < v[i]; j ++ )
    {
        int hh = 0, tt = -1;
        for(int k = j; k <= m;k += v[i] )
        {
            if(hh <= tt && k - (s[i] + 1)* v[i] + 1 > q[hh] )hh++;
            while(hh <= tt && f[i - 1][q[tt]] - (q[tt] - j)/v[i] * w[i] <= f[i - 1][k] - (k - j)/v[i] * w[i])tt -- ;
            q[++tt] = k;

            f[i][k] = f[i - 1][q[hh]] - (q[hh] - j)/v[i] * w[i] + (k - j)/v[i] * w[i];

        }
    }
}

cout << f[n][m] << endl;
return 0;

}