题目描述
https://www.acwing.com/problem/content/6/
算法1
(单调队列优化) $O(NV)$
一共 n 类物品，背包的容量是 m
每类物品的体积为v, 价值为w，个数为s
我们先来回顾一下传统的dp方程
dp[i][j] 表示将前 i 种物品放入容量为 j 的背包中所得到的最大价值
dp[i][j] = max(不放入物品 i，放入1个物品 i，放入2个物品 i, ... , 放入k个物品 i)
这里 k 要满足：k <= s, j - k*v >= 0
不放物品 i = dp[i-1][j]
放k个物品 i = dp[i-1][j - k*v] + k*w
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2*v] + 2*w,..., dp[i-1][j-k*v] + k*w)
实际上我们并不需要二维的dp数组，适当的调整循环条件，我们可以重复利用dp数组来保存上一轮的信息
我们令 dp[j] 表示容量为j的情况下，获得的最大价值
那么，针对每一类物品 i ，我们都更新一下 dp[m] --> dp[0] 的值，最后 dp[m] 就是一个全局最优值
dp[m] = max(dp[m], dp[m-v] + w, dp[m-2*v] + 2*w, dp[m-3*v] + 3*w, ...)
接下来，我们把 dp[0] --> dp[m] 写成下面这种形式
dp[0], dp[v], dp[2*v], dp[3*v], ... , dp[k*v]
dp[1], dp[v+1], dp[2*v+1], dp[3*v+1], ... , dp[k*v+1]
dp[2], dp[v+2], dp[2*v+2], dp[3*v+2], ... , dp[k*v+2]
...
dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j]
显而易见，m 一定等于 k*v + j，其中 0 <= j < v
所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的
也就是说，dp[k*v+j] 只依赖于 { dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] }
因为我们需要的是{ dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] } 中的最大值，
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题
所以，我们可以得到
dp[j] = dp[j]
dp[j+v] = max(dp[j] + w, dp[j+v])
dp[j+2v] = max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])
...
但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换
dp[j] = dp[j]
dp[j+v] = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w
...
这样，每次入队的值是 dp[j+k*v] - k*w
单调队列问题，最重要的两点
1）维护队列元素的个数，如果不能继续入队，弹出队头元素
2）维护队列的单调性，即：尾值 >= dp[j + k*v] - k*w
本题中，队列中元素的个数应该为 s+1 个，即 0 -- s 个物品 i
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int dp[N], pre[N], q[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
memcpy(pre, dp, sizeof(dp));
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) {
if (head <= tail && k - s*v > q[head])
++head;
while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
--tail;
if (head <= tail)
dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);
q[++tail] = k;
}
}
}
cout << dp[m] << endl;
return 0;
}
太难了吧
算法这东西确实是太抽象，但只要坚持，不管多难，也是一定能看懂的，要不那些大佬难道不是人是神吗？其实大多数人都一样的智力水平，除了yxc大佬 ，只不过有人快点，有人慢点，多比别人看几次，就能达到和别人一样的水平了。
dalao们帮忙看看哈
1.
if (hh <= tt && q[hh] < k - s * v) hh++;不是应该是0~s个物品i吗，不应该是(k-q[hh])/v>s+1移项吗？。？
2.
for (int k = j; k <= m; k += v)枚举余数为r类里的第k(此处的k用1~m的序号表示)个数
if (hh <= tt && q[hh] < k - s * v)hh++;去掉超出滑动窗口范围的元素//(k-q[hh])/v>s移项得q[hh] < k - s * v
因为k是 1~m下标除以v的余数r项的第k个数
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)tt--;是因为同一余数组别内的转移只需保留最大的价值
计算方法为(k - j) / v获取(真正的第k个数)，w获取价值
再根据 每次入队的值是g[k] - kw 维持单调递减序列
q[++tt] = k;把当前元素下标插入单调队列
f[k] = g[q[hh]] + (k - q[hh]) / v * w;计算f[k],右边为单调队列最大值,根据状态转移方程g[q[hh]]+k*w更新
f为最新状态，g为上一次状态，避免被干扰
看看是不是可以这么理解,哪里有错误望指正一下
写的好棒
好问题！确实是$0$~$s$共$s+1$个，按理说单调队列长度最长应该是$s+1$,这里为什么只有$s$个长度呢？
$DP$问题都可以视为一个填表求解的过程，比如本题就是一个二维表格的填充过程：
$f[i][j]$：前$i$个物品中选择，在体积上限是$j$的情况下，所能获取到的最大价值。
从上到下，从左到右去填表，我们发现了以下的事实：
$f[i-1][j] -> f[i][j]$
$f[i-1][j-v]+w -> f[i][j]$
$f[i-1][j-2v]+2w -> f[i][j]$
$f[i-1][j-3v]+3w -> f[i][j]$
....
$f[i-1][j-s*v]+s*w -> f[i][j]$
当然，这也不一定都对，因为要保证$j-s*v>=0$
这些数据依赖是 跳跃性的前序依赖，所以，我们按对体积取模的余数分组，按组讨论，就可以把二维表填充满。
它的前序依赖单元格个数是$s$(指最大值)个，我们需要在这些个值中找出一个$max$。这是一个 距离我最近$X$个元素内找出最大值的典型问题：单调递减队列求区间最大值，队头元素即答案。
$Q$:为什么是单调队列呢？如何运用单调队列求解呢？
就是维护一个队列，它是由大到小的顺序单调存在的。对于后面每一个加入进来的数据，因为它是最新出生的，就算是最小，当前面老家伙们死光后，它也可能成为掌门人(黄鼠狼下豆鼠子，一辈不如一辈，这种情况就是可能的~)，它必须保留！而它前面的老家伙，即使再厉害，由于年龄到了，也需要去世。没有来的及去世的老家伙们，因为能力值小于最后加入的数据，也就没有存在下去的必要，因为后面向前找，肯定先找到新出生而且能力值高的嘛，这些老家伙去世算了。
好了，我们成功的为最后加入的家伙找到了存在下去的必要性，没它可不行！！！
所以,我们视
f[i - 1][k]为新出生的家伙，用它与之前的老家伙们$PK$,而且，它还必须要参与到单调队列中去，它不能去世！如果被它占了一个名额后，就剩下$s$个位置了。
同时，我们也注意到，就是因为上面讨论到的原因，使得在执行
f[i][k] = f[i - 1][q[hh]] + (k - q[hh]) / v * w;之前，需要执行q[++tt]=k,让新出生的家伙进入队列，凑齐s+1个如果k体积，超出了当前物品的s个，这段代码有限制吗？
$j$ 是余数，$k$ 是实际值吗？
memcpy(pre, dp, sizeof(dp));这个是用来干什么的啊？
复制数组
《显而易见，m 一定等于 kv + j，其中 0 <= j < v
所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的
也就是说，dp[kv+j] 只依赖于 { dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[k*v+j] }
因为我们需要的是{ dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[k*v+j] } 中的最大值，
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题》
这一句为什么是 $if$ 而不是 $while$
假装给懂了的人回答：因为每次都只能弹出一个。
因为q内元素是递增的，假设对头为x，滑动窗口的范围为[l,r]，滑动窗口每次移动1，x出对的时候l=x+1，这时候队内的其他元素都是>x，所以不会出队。
因为每次最多入队一个啦 所以如果长度超了弹出一个就够了 当然 写while其实也行
显然这里是 k - s* v 与 q[head] 比较，
而非q[tail] ，你觉得呢？？
if (head <= tail && k - s*v > q[head])
++head;
这个弹出逻辑怎么解释?
滑动窗口长度为s
移项可得k-q[head]/v>s，也即判断队列中元素是否超过了窗口长度
这里滑动窗口长度必须为s吗，别的数可以吗
因为这里是选择0.1.2....s件物体
(k-q[head])/v > s
为什么更新dp[k]的时候要判断队列是否为空啊，什么情况下会为空啊？
好厉害
看了不下十篇题解，看到你这看懂了
“每次入队的值是 dp[j+kv] - kw” “q[++tail] = k;”这里的k不是列举的体积吗？为什么前面说要入队的值是一个f[i-1][j-kv]这样的东西？
想问一下 dp[k] 的更新是：1.在用pre[k]更新完队列之后还是 2.在用pre[k]更新完队列之前呢？我看其他的代码为什么是在用pre[k]更新完队列之前更新的 dp[k]，而这里是用pre[k]更新完队列之后更新的 dp[k]
那个“可以通过维护一个单调队列来得到结果。这样的话，问题就变成了j个单调队列的问题。”这里有点小错误，是变成了v个单调队列或者说j+1个单调队列才对
大佬牛逼，支持一波~
if (head <= tail)
dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w) 为什么不是 if (head <= tail)
dp[k] = max(dp[k], pre[q[head]] + (k - j）/v * w);
我觉得可以在 这样每次入队的值是 dp[j+kv] - kw 后面加上一句 k = { 1,2,....m/v}
~有用~# NB
##
STL不香嘛(小声BB）hh,这个数据卡stl
哦哦，
凉良心出题人队列也可以卡吗？
因为动态开点，确实慢
这里得用deque,queue不能队头弹出元素,deque的话速度极慢