---
title: "单调队列优化多重背包问题"
created: 2025-11-28
tags:
  - 算法
---

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

## 题目描述

有 n(0<n≤1000)种物品和一个容量为 V(0<V≤20000)的背包

第 i种物品最多有 si(0<si≤20000)件，每件体积是 vi(0<vi≤20000)，价值是 wi(0<wi≤20000)

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

## 多重背包—单调队列优化

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

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

f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,⋯,f(i−1,j−sv)+sw) **考虑用完全背包的优化方式来优化这个方程**

f(i,j−v)=max(f(i−1,j−v),f(i−1,j−2v)+w,⋯,f(i−1,j−(s+1)v)+(s)w) 写出这个公式好像并不是那么管用

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

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

但是，我们可以把这个式子 继续 推导下去，直到背包**体积被用到不能再用**为止

![[image-ecc03f84.png]]

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

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

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

为了方便观察，把 f(i−1,j)改写成 fj

![[image-982117dd.png]]

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

具体如下图：

![[image-ead7af88.png]]

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

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

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

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

要记得加上再比较

具体就是 当前下标 和该 最大值的下标 之间差了 x个 v，那么就要加上 x个 w 在上面公式里，还是比较容易看出的吧，就不做额外的推导了

## 代码

### 二维朴素版

时间复杂度：O(n×v)

空间复杂度：O(n×v)

滑动窗口的长度为 si+1

```cpp
#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;
}
```

### 一维优化

时间复杂度：O(n×v)

空间复杂度：O(v)

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

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

#### 拷贝数组写法

```cpp
#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;
}
```

#### 滚动数组写法

```cpp
#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;
}
```

作者：一只野生彩色铅笔 链接：<https://www.acwing.com/solution/content/53507/>

[AcWing 6. 多重背包问题 III - AcWing](https://www.acwing.com/video/218/)

这个视频讲的不是很清楚 和那个快慢指针似的 胡过去

提高课有视频 等买了回过头来想这个问题

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/简单DP相关模型/背包问题/多重背包练习/最大价值|最大价值]] 🏠 [[00-刷题理模型]] ➡️ [[多重背包问题|多重背包问题]]