python/TangDou/AcWing/BeiBao/6.md

## [$AcWing$ $6$. 多重背包问题 $III$](https://www.acwing.com/problem/content/6/)

### 一、题目描述
有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

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

**输入格式**
第一行两个整数，$N，V$ ($0<N≤1000, 0<V≤20000$)，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

**输出格式**
输出一个整数，表示最大价值。

**数据范围**
$0<N≤1000$

$0<V≤20000$

$0<v_i,w_i,s_i≤20000$

**提示**
> **本题考查多重背包的单调队列优化方法**。

**输入样例**
```cpp {.line-numbers}
4 5
1 2 3
2 4 1
3 4 3
4 5 2
```

**输出样例**：
```cpp {.line-numbers}
10
```

### 二、三种解法如何选择
三种解法的根本区别在于数据范围，题面都是一样的：

<!-- 让表格居中显示的风格 -->
<style>
.center 
{
  width: auto;
  display: table;
  margin-left: auto;
  margin-right: auto;
}
</style>
<div class="center">

| ① 朴素版本      | ② 二进制优化版本  | ③ 单调队列优化版本 |
| --------------- | ----------------- | ------------------ |
| $n≤100$,$V≤100$ | $n≤1000$,$V≤2000$ | $n≤1000$,$V≤20000$ |
</div>

> **温馨提示**：~~其实啊，三种都需要熟练背下来，谁知道考试时出题人会从哪个版本出发搞你~~


### 三、单调队列优化
使用朴素版本利用数据进行调试，找一下规律，看看哪个状态间存在转移关系：

```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int n, m;
int v, w, s;
int f[N];

/**
 * 测试用例:
 2 9
 3 5 2
 2 4 3
 */
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        cin >> v >> w >> s; //体积、价值、数量
        //一维是倒序，而且最小值可以到达v
        for (int j = m; j >= v; j--)
            for (int k = 0; k <= s && j >= k * v; k++) {
                f[j] = max(f[j], f[j - k * v] + k * w);
                //输出中间过程，用于调试，找规律
                printf("f[%d]=%2d f[%d]+%d=%d\n", j, f[j], j - k * v, k * w, f[j - k * v] + k * w);
            }
    }
    return 0;
}
```
<center><img src='https://img2022.cnblogs.com/blog/8562/202201/8562-20220126104409857-886115013.png'></center>

#### 原理解析

多重背包:物品个数是复数个，但又不是无限个。
- 当作$01$背包来理解，$s$个物品当成$s$次$01$背包操作。然后优化的话通过 **二进制** 来优化。
- 当作完全背包来理解，就是有数量限制的完全背包，而这个数量限制就可以理解成 **滑动窗口的长度**,然后优化通过 **单调队列** 来优化。

队列的单调性就是基于
$$f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w,.....,f[i - 1][j - k * v] + k * w$$

要将前$i - 1$个物品的方案基础上不停尝试放入第$i$个物品，遍历取最大值。
$f[i - 1][j - k*v] + k *w$表示，总空间是$j$，有且仅有$k$个物品$i$，其余空间通过前$i - 1$个物品填充的最大价值。

多重背包因为有数量限制，向前遍历的个数$k$是受到数量$s$限制的。

所以要将$max$中的每个元素$f[i - 1][j], f[i - 1][j - v] + w,.....,f[i - 1][j - k * v] + k * w$，通过维护单调队列，来获得当前窗口宽度$s$范围内的最大值。

并且在$j = j + v$后，队列中所有元素对应状态与当前背包空间差增加了$v$，可以多放一个物品$i$，每个元素对应的价值增加$w$，全部都加一个$w$，所以单调性不发生任何变化。

两种优化可以理解成两种思路的进化路线。

#### 二维版本
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;  // 物品种类上限
const int M = 20010; // 背包容量上限
int n, m;

int f[N][M]; // 前i个物品，在容量为j的限定下，最大的价值总和
int q[M];    // 单调优化的队列,M是背包容量上限，说明q[]里面保存的是体积

// 二维+队列[k-s*v,k],队列长s+1
int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) { // 考虑前i种物品
        int v, w, s;               // 体积、价值、个数
        cin >> v >> w >> s;
        // 下面的j,k是一起用来描述剩余体积的,之所以划分成两层循环，是因为依赖的前序是按v为间隔的依赖，并且，是有个数限制的依赖
        // j:按对体积取模分组：0表示剩余空间除以当前物品的体积余数是0
        // k:分组内的每一个体积,注意：这里的体积不一定都是合法的，因为数量是有限制的
        // 单调队列的意义：查找前面k-s*v范围内的价值的最大值，是一个单调递减的队列，队头保存的是获取到最大值的最近体积
        for (int j = 0; j < v; j++) {         // 按余数分组讨论
            int hh = 0, tt = -1;              // 全新的单调下降队列
            for (int k = j; k <= m; k += v) { // 与j一起构成了有效体积
                // 1、讨论到第i个物品时，由于它最多只有s个，所以有效的转移体积最小是k-s*v,更小的体积将被去除
                if (hh <= tt && q[hh] < k - s * v) hh++;
                // 2、处理队尾,下一个需要进入队列的是f[i-1][k]，它是后来的，生命周期长，可以干死前面能力不如它的所有老头子,以保证一个单调递减的队列
                while (hh <= tt && f[i - 1][q[tt]] + (k - q[tt]) / v * w <= f[i - 1][k]) tt--;
                // 3、k入队列
                q[++tt] = k;
                // 4、队列维护完毕，f[i-1][k]已经进入队列,f[i][k]可以直接从队头取出区间最大值更新自己
                f[i][k] = f[i - 1][q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

```


#### 一维版本
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int f[M], g[M];
int q[M];
int v, w, s;
// 一维写法
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        memcpy(g, f, sizeof g);
        cin >> v >> w >> s;
        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++;
                while (hh <= tt && g[k] >= g[q[tt]] + (k - q[tt]) / v * w) tt--;
                q[++tt] = k;

                f[k] = max(g[k], g[q[hh]] + (k - q[hh]) / v * w);
            }
        }
    }
    printf("%d\n", f[m]);
    return 0;
}
```

### 七、疑问与解答　

#### $Q_1$:单调队列中装的是什么？
$A$:是体积，是$f[i][j]$可以从哪些 **体积** 转移而来。比如当前$i$物品的体积是$v_i=2$,个数是$3$，那么$f[i][j]$可以从
$$
\large \left\{\begin{array}{l}
 f[i-1][j-v_i*0]+0*w_i& 选择0个 \\ 
 f[i-1][j-v_i*1]+1*w_i& 选择1个\\ 
 f[i-1][j-v_i*2]+2*w_i& 选择2个 \\ 
 f[i-1][j-v_i*3]+3*w_i& 选择3个 
\end{array}\right.
$$
转移而来，也就是$(j-v_i*0,j-v_i*1,j-v_i*2,j-v_i*3)$这四个中的一个。

当然，还需要判断一下是不是你的背包能装下那么多，一旦装不下了就别硬装了。

#### $Q_2$:只记录体积怎么计算最大价值？
$A$:只记录了所关联的体积，最大价值是现算:
$$\large f[i][k] = f[i - 1][q[hh]] + (k - q[hh]) / v * w$$

即，自己的最优解，可以通过前序当中 **最大值** 所在的体积`q[hh]`转移而来，增量价值是 $\large \displaystyle (k - q[hh]) / v * w$

#### $Q_3$:单调队列的使用场景在哪里？
$A$:使用单调队列的 **唯一场景** 就是 **离我在$S$的范围内，最大或最小值是多少**?
它的任务是做到$O(1)$的时间复杂度进行快速查询结果，所以，只能是放在队首，不能再进行遍历或者二分，那样就不是$O(1)$了。

#### $Q_4$:单调队列是怎么样做到将最优解放到队首的呢？
$A:$单调队列优化有三步曲，按套路做就可以完成这样的任务：
* 将已经超过 **窗口范围** 的旧数据从单调队列中去掉，保证窗口中只有最近的、最多$s$个(或$s+1$,这和具体的题意有关，后续会继续说明~)有效数据。
  
* 利用队首中保存的体积，我们知道最大值的前序体积$q[hh]$,从这个体积转移而来就行。
  $$\large f[i][k] = f[i - 1][q[hh]] + (k - q[hh]) / v * w$$

* <font color='red' size=4><b>滑动窗口是建立在前序数组$f[i-1]$上的，范围只能是前面一行$f[i-1][j],f[i-1][j-v],f[i-1][j-2v],...,f[i-1][j-kv]$</b></font> 

#### $Q_5:$此处的单调队列，是递增还是递减的？
$A:$是一个单调递减的队列,队列头存储的是窗口中的最大值所对应的体积。

#### $Q_6$:为什么要先进队列，再更新答案呢？我看有些同学是先更新答案，再进队列啊？
$A$:这个主要看$f[i-1][k]$是不是可以成为答案的备选项，如果是，那么就先进队列，再更新；如果不是，则先更新再进队列。以本题为例，$f[i][k]$可不可以从$f[i-1][k]$迁移而来呢？从实际含义出发，是可以的，这表示：第$i$个物品一个也不要，在空间最大是$k$的情况下，最大值如何表示？此时，当然最大值表示为$f[i-1][k]$了，即可以成为答案的备选项，需要先进队列再更新答案。

#### $Q_7$:`if (hh <= tt && q[hh] < k - s * v) hh++;`
不是应该是$0$~$s$个物品$i$吗，不应该是$(k-q[hh])/v>s+1$个项吗？

**答**：好问题！确实是$0$~$s$共$s+1$个，按理说单调队列长度最长应该是$s+1$,这里为什么只有$s$个长度呢？

$DP$问题都可以视为一个填表求解的过程，比如本题就是一个二维表格的填充过程：
$f[i][j]$：前$i$个物品中选择，在体积上限是$j$的情况下，所能获取到的最大价值。
从上到下，从左到右去填表，我们发现了以下的事实：

- 每一个二维表中的位置，都是可以从上一行中的某些位置转移而来的。比如：

$f[i-1][j]      \rightarrow    f[i][j]$

$f[i-1][j-v]+w \rightarrow   f[i][j]$

$f[i-1][j-2v]+2w \rightarrow   f[i][j]$

$f[i-1][j-3v]+3w \rightarrow   f[i][j]$

....

$f[i-1][j-s*v]+s*w \rightarrow  f[i][j]$

当然，这也不一定都对，因为要保证$j-s*v>=0$

这些数据依赖是 **跳跃性的前序依赖**，所以，我们按对体积取模的余数分组，按组讨论，就可以把二维表填充满。

- 它的前序依赖单元格个数是$s$(指最大值)个，我们需要在这些个值中找出一个$max$。这是一个距离我最近$X$个元素内找出最大值的典型问题：单调递减队列求区间最大值，队头元素即答案。

- **$Q$:为什么是单调队列呢？如何运用单调队列求解呢？**
就是维护一个队列，它是由大到小的顺序单调存在的。对于后面每一个加入进来的数据，因为它是最新出生的，就算是最小，当前面老家伙们死光后，它也可能成为掌门人(黄鼠狼下豆鼠子，一辈不如一辈，这种情况就是可能的~)，它必须保留！而它前面的老家伙，即使再厉害，由于年龄到了，也需要去世。没有来的及去世的老家伙们，因为能力值小于最后加入的数据，也就没有存在下去的必要，因为后面向前找，肯定先找到新出生而且能力值高的嘛，这些老家伙去世算了。

好了，我们成功的为最后加入的家伙找到了存在下去的必要性，没它可不行！！！

所以,我们视`f[i - 1][k]`为新出生的家伙，用它与之前的老家伙们$PK$,而且，它还必须要参与到单调队列中去，它不能去世！
> $Q$:为啥要视它为最新出生的家伙，咋不视别人呢？
> $A$:往前倒着看，离自己最近，谁最近？因为这里的距离其实是按体积看的，和自己一样体积的单元格，在自己的正上方，上可以转移到$f[i][j]$的吧，$f[i-1][k]$当然是最后一个啦。

如果被它占了一个名额后，就剩下$s$个位置了。

同时，我们也注意到，就是因为上面讨论到的原因，使得在执行`f[i][k] = f[i - 1][q[hh]] + (k - q[hh]) / v * w;` 之前，需要执行 `q[++tt]=k`,让新出生的家伙进入队列，凑齐`s+1`个