多重背包

Problem Description
急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？

Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

Output
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

Sample Input

1
8 2
2 100 4
4 100 2

Sample Output

400

解题思路

其实这就是多重背包，但会发现用最赤裸裸的方法是过不了的，连二进制优化也都不行。那下面就来介绍一下用单调队列来实现的时间复杂度为O(nm)的多重背包。
先回顾最赤裸裸的多重背包做法。
For (int i=1;i<=n;i++)
For (int j=m;j>=0;j–)
For (int k=1;k<=s[i]&&k乘w[i]>=j;k++)
F[j]=min(f[j],f[j-k乘w[i]]+v[i]乘k);
很显然前两个循环是少不了的，那么我们来想如何去掉第三个循环，从而使时间复杂度变为我们想要的O(nm)。
优化的原理是啥呢？w[i]表示物品重量，v[i]表示价值，c[i]表示数量，我们知道朴素状态转移方程：
令 c[i] = min(num[i], j / w[i])
f[i][j] = max(f[i-1][j-k 乘 w[i]] + k 乘v[i]) (1 <= k <= c[i]) 这里的 k 是指取第 i 种物品 k 件。

如果令 a = j / w[i] , b = j %w[i] 那么 j = a 乘 w[i] + b.
这里用 k 表示的意义改变， k 表示取第 i 种物品的件数比 a 少几件。
那么 f[i][j] = max(f[i-1][b+k乘w[i]] - k乘v[i]) + a乘v[i] (a-c[i] <= k <= a)
可以发现，f[i-1][b+k乘w[i]] - k乘v[i] 只与 k 有关，而这个 k 是一段连续的。我们要做的就是求出 f[i-1][b+k乘w[i]] - k乘v[i] 在 k 取可行区间内时的最大值。

这就可以使用单调队列优化。发现在模v[i]的同一个剩余类下的所有体积的决策点都是连续的（虽然看起来是离散，但是是连续的离散），可以用单调队列维护，所以我们先按照剩余类分类，对于每一个剩余类用一个单调队列维护，这样时间复杂度就只有O(nm)

实际就是用一个数枚举余数，一个数枚举当前余数有多少个
如：
n=10 ·
1 4 7 10
2 5 8
3 6 9
这里就可以按余数分为三组（每一组里面的数都有一定关系，但每一组和其他的组却一点关系都没有）
然后我们可以通过单调队列在每一组都循环一下

AC代码

#include<iostream>
using namespace std;
long long T,n,m,w,v,num,head,tail,f[105],q[105],p[105];
int main()
{
   
	cin>>T;
	while(T--)
	{
   
		cin>>n>>m;
		for(int i=0;i<=n;i++)f[i]=0;//清零（多种数据）
		for(int i=1;i<=m;i++)
		{
   
			cin>>w>>v>>num;
			for(int d=0;d<w;d++)//模拟余数
			{
   
				head=tail=1;//初值
				for(int j=0;j<=(n-d)/w;j++)//（n-d）/w指当前余数有多少个
				{
   
					int o=f[j*w+d]-v*j;//要进队列的值
                    while(q[tail-1]<=o&&head<tail)tail--;//弹出队尾
                    q[tail]=o;//进队
					p[tail++]=j;//下标
                    while(j-p[head]>num&&head<tail)head++;//弹出队头
                    f[j*w+d]=max(f[j*w+d],q[head]+v*j);//找最大值
				}
			}
		}
		cout<<f[n]<<endl;
	}
}

谢谢