<—点个赞吧QwQ

宣传一下算法提高课整理

有 $N$ 种物品和一个容量是 $V$ 的背包。

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

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

输入格式

第一行两个整数，$N，V$ $(0 \lt N \le 1000$, $0 \lt V \le 20000)$，用空格隔开，分别表示物品种数和背包容积。

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

输出格式

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

数据范围

$0 \lt N \le 1000$
$0 \lt V \le 20000$
$0 \lt v_i, w_i, s_i \le 20000$

提示

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

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

思路1

$f_{i,j}=\max{\{f_{i - 1,j},f_{i-1,j - w} + v,f_{i-1,j - 2\times w} + 2\times v, \cdots,f_{i-1,s\times w} + s\times v\} }$
$f_{i,j-w}=\max\quad~ ~{\{f_{i-1,j-w}\quad~ ~ ~,f_{i - 1,j-2\times w} + \quad~ ~ ~ v,\cdots,f_{i-1,s\times w} + (s-1)\times v,f_{i-1,(s + 1)\times w} + s\times v\} }$

这里我们就只多了一项，而$\max$不满足区间减法，所以分析失败。

天无绝人之路（$y$的名言），我们再次开始，我们分成$\lfloor \frac{j}{w}\rfloor$组，每组里的所有数是分别是：
$f_{i-1,r},f_{i-1,r + w},\cdots,f_{i-1,j-w},f_{i-1,j}$，其中$r=j \bmod w$，那我们该怎么维护呢?
假设当前维护到了第$r+i\times w$的位置，则我们要用到的区间就是包括当前点以及从这个点开始往前数的$s-1$的个点（也就是$s$个点）。由于我们每次不要第一个数，加上后一个数，再求最大值，不就是单调队列的功能吗？我们使用单调队列，让复杂度降至$O(nm)$

代码1

#include <iostream>
using namespace std;
const int N = 1010,M = 20010;
int n,m;
int f[N][M];
int q[M],hh,tt;
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v,s;
        cin >> w >> v >> s;
        for (int r = 0;r <= w - 1;r++) {
            hh = 0,tt = -1;
            for (int j = r;j <= m;j += w) {
                while (hh <= tt && q[hh] < j - w * s) hh++;
                while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / w * v <= f[i - 1][j]) tt--;
                q[++tt] = j;
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / w * v;
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

思路2

由于只用到了第$i-1$层和第$i$层两层之间转移状态，所以我们可以采用滚动数组优化。

代码2

#include <iostream>
using namespace std;
const int N = 20010;
int n,m;
int f[2][N];
int q[N],hh,tt;
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v,s;
        cin >> w >> v >> s;
        for (int r = 0;r <= w - 1;r++) {
            hh = 0,tt = -1;
            for (int j = r;j <= m;j += w) {
                while (hh <= tt && q[hh] < j - w * s) hh++;
                while (hh <= tt && f[i - 1 & 1][q[tt]] + (j - q[tt]) / w * v <= f[i - 1 & 1][j]) tt--;
                q[++tt] = j;
                f[i & 1][j] = f[i - 1 & 1][q[hh]] + (j - q[hh]) / w * v;
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}