单调队列优化法
从公式入手来看是否还有可以改进的地方
\(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-s_i*v]+s_i*w)\)
我们可以发现该方程的第二维是 \(j-v,j-2*v,j-3*v,j-s_i*v\) ，因为受到完全背包的感染，所以写以下\(dp[i][j-v]\)的方程来对比看一下。
\[dp[i][j - v] =max(dp[i-1][j - v],dp[i-1][j -2 * v]+w\\ ,...,dp[i-1][j-s_i*v]+(s_i-1)*w) + dp[i-1][j-(s_i+1)v + w*s_i] \]
从图中可以看出来，可以看出来一开始是匹配的，但是最后一个不匹配，也就是 \(j\) 没有 \(j-v\) 的最后一项，所以
\[max(dp[i - 1][j],dp[i-1][j - v] + w,dp[i-1][j -2 * v] + 2*w,...,dp[i-1][j-s_i*v]+s_i*w)\\ \not=\\ max(dp[i-1][j - v],dp[i][j - v] + w) \]虽然猜想不对，但是我们发现了 \(dp[i][j]\) 对比 \(dp[i][j-v]\) 的方程中间有一大部分是匹配的，而且是后面少一项和前面多一项的关系，想利用这一部分，就想到了一个非常匹配这个过程的方法--------滑动窗格。
为了方便表述，我们这里使用滚动数组，将 \(dp[i -1][j]\) 的值全部存在\(pre\)数组里面。\(pre[j] = dp[i-1][j]\)
\(pre[j]\) 的含义是从前 \(i-1\) 个物品中选，且体积不超过 \(j\) 的最大价值。
那么假设 \(s_i\)==3，\(dp[i][j] = max(pre[j],pre[j-v]+w,pre[j-2*v]+2*w,pre[j-3*v]+3*w)\)
可以看出来，当前的窗格需要从前面往后推,然后边推还可以边把 \(dp[i][j - v],dp[i][j-?*v]\)全给赋值了，然后可以发现以下两点
-
不能像暴力法那样，直接丢掉一维，不然你求 \(j-5*v\) 的时候，要用到 \(j-6*v\) 已经被覆盖掉了，所以用一个滚动数组 \(pre\) 来存储
-
因为前往后推，所以我们先要找到起点的体积比如说上图就是 \(j-6*v\) ,假设 \(0<j-6*v<v\)。
起点有 0 到 \(v-1\) 种可能，那么我们这里就可以换一种写法了比如说
\[假设j-6*v = 2,0<2<v\\ 那么j - 5*v = 2+v,\;j-4v=2+2*v...j = 2 + 6*v\\ 去掉等号一边就是 2,2+v,2+2*v,...,2+6*v\\ 那么max(pre[j],pre[j-v]+w,pre[j-2*v]+2*w,pre[j-3*v]+3*w)\\ 变成max(pre[2 + 6*v],pre[2 + 5*v]+w,pre[2 + 4*v]+2*w,pre[2 + 3*v]+3*w) \]上面是具体的写法，下面将其抽象化：总体积 \(m = k*v+j，0<j<v\),先不管后面加的部分
\[pre[j],pre[j+v],pre[j + 2 *v],pre[j + 3*v],...,pre[j + k*v] \]写到这里，我们发现，其实我们枚举 \(0<j<v\) 然后一直推到这个\(j\) 对应的结尾就可以完成这个物品的更新了。这里补全一下抽象化后的整个表示
\[pre[0] , pre[v], pre[2*v], pre[3*v], ... , pre[k*v]\\ pre[1], pre[v+1], pre[2*v+1], pre[3*v+1], ... , pre[k*v+1]\\ pre[2], pre[v+2], pre[2*v+2], pre[3*v+2], ... , pre[k*v+2]\\ pre[3], pre[v+3], pre[2*v+3], pre[3*v+3], ... , pre[k*v+3]\\ ...\\ pre[j], pre[v+j], pre[2*v+j], pre[3*v+j], ... , pre[k*v+j]\\ 每一行滑动过去，比如s = 3的话,一开始是j,v+j,2*v+j\\下一个就是v+j,2*v+j,3*v+j这样边滑边更新 \]然后现在知道怎么更新，还知道怎么全部都更新，剩下的就是怎么快速的找到滑动窗格的最大值，那么单调队列登场。
另起一个数组为 \(q[N]\) ，里面存的是背包的体积，设置队列头为 \(head\) ,尾巴为 \(tail\) \(q[头, , , ,...,尾巴]\) ,保证队列里面是单调的，也就是 \(head\) 代表的体积的价值 \(\ge tail\) 代表的体积的价值。
现在问题来到怎么维护单调队列的单调性?
当前的背包体积 \(k\)，因为要单调队列的单调性，所以要找到一个合适的位置讲当前背包放入队列中，这个合适的位置的体积的最大价值大于体积k的最大价值才行，\(pre[q[tail]]\) 取得的就是当前尾部体积的价值相当于\(dp[i - 1][q[tail]]\) 和当前的价值 \(dp[i-1][k]\) 比较，有没有发现什么不对劲？
\(pre[j]\)的含义是从前\(i-1\)个物品中选，且体积不超过\(j\)的最大价值。\(pre[h] = dp[i-1][h]\)
\(dp[i][j] = max(dp[i - 1][j],dp[i-1][j - v] + w,...,dp[i-1][j-s_i*v]+s_i*w)\)
看了眼原始方程，回忆下变量的含义。没错漏掉了\(k - q[tail]\)这部分给\(dp[i - 1][q[tail]]\)带来的价值，所以比较的时候要给加回去继续比较，那么就可以写出这部分的代码了
可以对比起来看一下
\[dp[i-1][j - ?*v] + ?*w\\ = pre[q[tail]] + (k - q[tail]) / v * w \]while (head <= tail && pre[q[tail]] + (k - q[tail]) / v * w <= pre[k])
tail--;
时间复杂度：
\(O(物品数列*背包体积)=O(N*V)\)
实现：
接下来直接看完整代码就可以了：
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20005;
// pre存储i - 1的时候的值
// q为偏移量为?时候的单调队列
int dp[N], pre[N], q[N], n, m;
int main()
{
//n为物品的总数，背包容量为m
scanf("%d%d", &n, &m);
while (n--)
{
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
//赋值上一层结果
memcpy(pre, dp, sizeof(dp));
//枚举偏移量(起点)
for (int i = 0; i < v; i++)
{
//建新的单调队列 头>>>尾巴，里面存的是体积
int head = 0, tail = -1;
//更新该起点代表的行,k是此时的体积
for (int k = i; k <= m; k += v)
{
//判断窗格是否超过了k,头需要往后滑动
if (head <= tail && k - q[head] > s * v)
head++;
//赋值
//pre[q[head]]+(k - q[head]) / v * w)：前i-1个中选，且体积不大于q[head]的最大价值 + 第i个物品选(k - q[head]) / v 个的价值
if (head <= tail)
dp[k] = max(dp[k], pre[q[head]] + (k - q[head]) / v * w);
//队列中加入k,并且维护队列单调性
//pre[k]：前i-1个中选，且体积不大于q[head]的最大价值 + 第i个物品选0个
//pre[q[tail]] + (k - q[tail]) / v * w ：前i-1个中选，且体积不大于q[tail]的最大价值 + 第i个物品选(k - q[tail]) / v个
while (head <= tail && pre[q[tail]] + (k - q[tail]) / v * w < pre[k])
tail--;
q[++tail] = k;
}
}
}
printf("%d", dp[m]);
return 0;
}