注意事项：
难度警告！本题为楼教主男人八题之一，量力而行！
本题为"dp动态规划—多重背包" 和"单调队列—滑动窗口"的组合扩展题，请一定确保完全清晰理解这两题再来！

题目：
有 N种物品和一个容量是 V的背包。
第 i种物品最多有 si件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V (0 接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。

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

数据范围
0 0 0

输入:
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出：
10

#include 
#include 
#include 
#include 
using namespace std;const int N = 20010;
int n, m;
int v[N], w[N], s[N];
int f[N][N], q[N];          //q为滑动区间，维护的是一个单调递减的队列，确保队头，也就是最左侧的元素始终为最大值, 注意，q中存储的是下标不是实际值int main()
{//读入cin >> n >> m;for (int i = 1; i<=n; i++) cin >> v[i] >> w[i] >> s[i];//第一层循环i是物品for (int i = 1; i<=n; i++) {//第二层循环r是体积，但这里的这个体积指的是(体积 % v)剩下的reminder余数for (int r = 0; r < v[i]; r++) {//然后这里就是滑动区间的模板做一些调整，建议先去看懂滑动区间那道题。//第三层循环决策，在相同的余数区间内，找到滑动区间的最大值(这里请务必去看彩铅大佬的题解，两句话解释不清楚)int hh = 0, tt = -1;for (int j = r; j <= m; j += v[i]) {//当队列不空，且 滑动区间内的总体积 超过s[i]*v[i]也就是选取s个i的体积时，将队头元素弹出if (hh <= tt && (j-q[hh])/v[i] > s[i]) hh++;//保证队列的单调下降性质//(j-q[tt])/v[i]是计算队头和j之间差了k个数，乘w[i]是因为实际上队头和j之间还差了k个w[i]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;
}

思路：
强烈推荐先看"多重背包问题 III y总讲解"视频，
再看" 一只野生彩色铅笔/多重背包问题 III"这篇题解

彩铅大佬的题解讲的已经非常清晰，就这样我还整整花了三个小时才理解思路，实在是怕误人子弟，这题就不写题解了（

我这里写的是二维朴素版本，更好理解一些，彩铅大佬的题解里有一维优化以及滚动数组优化的版本。

ps：现在人都是麻的，从16点看到23点QAQ

声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流