背包问题总览

既然是从基础开始复习，那么背包问题这种经典的问题就必不可少，这里来总结一下各类的背包问题。

01背包问题

非常经典的入门级问题，题目描述就不说了。
直接dp，可以设$f[i][j]$表示取到第i个，已经用了j的空间的最大价值。
状态转移方程：$f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i])$
关于空间的优化： 可以发现只有$f[i-1]$对当前的$f[i]$有影响，因此我们可以用$f[0、1]$
当然更简单可以直接用$f[j]$，当然这种情况就要j倒过来枚举，具体原因很简单：前面是上一次的，如果覆盖了，就等于重复取这个一次的了。
代码不贴了
时间复杂度是$O(NM)$
N:物品个数；M：背包空间

完全背包问题

题目就是在01背包的基础上让每一个物品都可以无限次地取。
那么这个问题上面我们已经说过了：
在刚才压缩空间操作地时候，只用$f[j]$的时候，我们提到了要把j反过来枚举，否则就相当于可以重复取同一个了。那么刚好就满足了我们这个问题的要求，所以我们只需要正向枚举j就行。
时间复杂度:$O(NM)$

分组背包问题

题目是给你几组物品，每一组内的物品我们最多只能取一个，求最大价值
那么很容易想到在最外面枚举每个组，这样就可以使组与组之间独立开，方便内部操作。
然后我们再枚举空间，最后再枚举组内物品，这样的顺序可以保证不会出现组内物品重复取的问题。
（试想，如果先枚举物品再枚举空间，那么就相当于每一个物品都用空间算了一次，那么自然组内的物品就有可能重叠。）
时间复杂度:$O(NM)$
N表示物品总数；M表示空间

多重背包问题

全部里面最难的问题，可以理解为限制最多的背包问题。
对于每个物品，我们有$s[i]$表示此物体最多能被取的个数

简单的暴力思路：

在01背包的基础上枚举每个物体取的个数，上限是$s[i]$
时间复杂度就是$O(NM\sum s[i])$

进阶版的优化思路：（二进制优化）

想到可以把是每个物体的$s[i]$个都拆开，变成$s[i]$个物体，再做01背包
但是这样的复杂的是和上述暴力一样的
那么在拆分的时候我们可以考虑二进制拆分，即把$s[i]$拆成$C+\sum 2^i$
其中C是余数，这样就可以把$s[i]$分为$logs[i]$份，时间复杂度就可以做到$O(NMlog\overline{s})$
正确性证明：
对于

终极版优化：（单调队列优化）

此优化是单调队列的一个常见用法，用于求移动区间的最大最小值
首先我们要知道，单调队列是什么：
就是一个尾进头出的队列，如果是维护最大值，那么此队列就是从大到小的。维护时我们只需要保证队列的单调性即可。具体操作就是用即将入队的元素与队尾比较，如果队尾更小，就直接出队，直到遇到比它大的位置，最后再将该元素入队。
那么在这里怎么使用呢？
首先看转移的路径：
假设此物体的空间是3，那么对于$f[i]$可以从$f[i-3]$、$f[i-6]$、$f[i-9]$等转移过来，当然个数有限制。
那么对于这样的下标是等差数列的元素，与其他等差数列中的数显然是相互独立的，那么就可以分开处理。
所以对于这样的每个等差数列，我们可以维护一个单调队列，（注意判断个数限制）每次取队首就可以了。
时间复杂度就是$O(NM)$
打法有两种，一种是全部一起处理，把一个单调队列分为好多块…很繁琐，不推荐。

for (i=1;i<=n;++i){
		memcpy(f[0],f[1],sizeof(f[1]));
		memset(que,0,sizeof(que));
		memset(head,0,sizeof(head));
		memset(tail,0,sizeof(tail));
		
		for (j=1;j<=w[i];++j){
			head[j]=tail[j]=j;
			que[j]=j-1;
		}
		for (j=w[i];j<=m;++j){
			x=(w[i]==1)?1:j%w[i]+1;
			while(head[x]<=tail[x]&&(j-que[head[x]]>s[i]*w[i])) head[x]+=w[i]; 
			f[1][j]=max(f[1][j],f[0][que[head[x]]]+v[i]*(j-que[head[x]])/w[i]);
			while(head[x]<=tail[x]&&(f[0][que[tail[x]]]+v[i]*(j-que[tail[x]])/w[i]<f[0][j])) tail[x]-=w[i];
			tail[x]+=w[i];
			que[tail[x]]=j;
			
			ans=max(ans,f[1][j]);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

当然清晰又简单的是可以分组来进行，分别枚举每个等差数列：

for (i=1;i<=n;++i){
		memcpy(f[0],f[1],sizeof(f[1]));
		
		for (j=0;j<w[i];++j){
			head=0,tail=-1; 
			
			for (k=j;k<=m;k+=w[i]){//k为等差数列的每个元素
				while(head<=tail && k-que[head]>s[i]*w[i]) head++; 
				
				if(head<=tail) f[1][k]=max(f[1][k],f[0][que[head]]+v[i]*(k-que[head])/w[i]);
				
				while(head<=tail && f[0][que[tail]]+v[i]*(k-que[tail])/w[i]<=f[0][k]) tail--;
				
				que[++tail]=k;
				
				ans=max(ans,f[1][k]);
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

那么这个问题就结束了，理解起来有一点困难。