这个是我最近最引以为傲的理解，（大佬勿喷），咱们话不多说直接上题

模板题来自acwing多重背包问题Ⅲ

 圣人惠额滴神啊！！！！

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

这里dp的思路：q[l]是小于等于l体积所能装下的价值最大值，k个物品，j遍历的是V/vi的余数，思路的核心，就是利用q[l]来储存体积从j=0到余数的价值最大值直接进行相加，省略了类似01背包组合物品的思想，直接维护以一个体积能装下的价值最大值。再用这个储存的最大值来进行递推。

递推式如下：

dp[k*vi+j]=max(dp[k*vi+j],q[l]+k*wi);

了解了思路就要想办法实现了，怎么才能完成一个单调队列获得一段数列中的最大值呢 ？

int temp=dp[k*vi+j]-k*wi;
while(l<r&&q[r-1]<=temp)r--;
q[r]=temp;
num[r++]=k;
while(l<r&&k-num[l]>si)l++;

这里给出代码，明天给出单调队列的思路 （孩子累了。。。。明天写完加上传送门）

给出ac代码

#include<bits/stdc++.h>
using namespace std;
int dp[200005],q[500000],num[100005];
int l,r;
int main(){
	int n,v;
	cin>>n>>v;
	int vi,wi,si;
	for(int i=1;i<=n;i++){
		cin>>vi>>wi>>si;
		if(si>v/vi)si=v/vi;
		for(int j=0;j<vi;j++){
			l=r=1;
			for(int k=0;k<=(v-j)/vi;k++){
				int temp=dp[k*vi+j]-k*wi;
				while(l<r&&q[r-1]<=temp)r--;
				q[r]=temp;
				num[r++]=k;
				
				while(l<r&&k-num[l]>si)l++;
				dp[k*vi+j]=max(dp[k*vi+j],q[l]+k*wi);
			}
		}
	}
	cout<<dp[v];
	
}

给个小问题：输出的为什么是dp[V]，为什么不是在dp数组中遍历寻找最大值？

其实想法和上期讲01背包的初始化相似，当维护q[l]时，0体积0价值的物品仍是合法存在的。

梳理几种背包优化方式和困惑（第一期）_我们教练不会签到的博客-CSDN博客