五类背包问题总结笔记

本文主要描述背包问题的常见类型。

01背包

问题描述

有$n$种物品，每个物品有两个属性：代价与价值。每种物品只能选一个，给定一个载代价为$m$的背包，求可以获得的价值最大值。

题解

设$f[i,j]$表示前$i$种物品占用$j$代价后能够得到的最大价值。
分装与不装$i$物品进行讨论。

$$f[i,j]=\max \begin{cases} f[i-1,j-w[i]]+c[i] & \text{装}i\text{物品} \\ f[i-1,j] & \text{不装}i\text{物品} \end{cases}$$

因此我们可以在$O(nm)$的时间内求出答案。

for(int i=1; i<=n; i++)
	for(int j=0; j<=m; j++) {
		f[i][j]=f[i-1][j];
		if(j>=cost[i])f[i][j]=max(f[i][j],f[i][j-cost[i]]+value[i]);
	}

优化1

发现第一维始终是从上一个转移而来，故省去第一维。
为了避免重复转移，将循环改为倒序枚举。

for(int i=1; i<=n; i++)
	for(int j=m; j>=cost[i]; j--)
		f[j]=max(f[j],f[j-cost[i]]+value[i]);

优化2

若只判断是否可达某个状态，而不要求求最大价值，可以使用bitset进行优化。
设$f[i,j]$表示前$i$种物品能否花费$j$的代价。
将其压缩为bitset。

for(int i=1; i<=n; i++)f[i]=(f[i-1]>>cost[i])|f[i-1];

若要压缩空间可直接开一个bitset的变量即可。

完全背包

问题描述

有$n$种物品，每个物品有两个属性：代价与价值。每种物品只能选可以选无限个，给定一个载代价为$m$的背包，求可以获得的价值最大值。

题解

与01背包不同在于可以多次选择，只需要将转移方程稍微改一下即可：

$$f[i,j]=\max \begin{cases} f[i,j-w[i]]+c[i] & \text{装}i\text{物品} \\ f[i-1,j] & \text{不装}i\text{物品} \end{cases}$$

优化

发现第一维始终是从上一个转移而来，故省去第一维。
与01背包不同在于，可以多次选择，故不需要倒序枚举。

for(int i=1; i<=n; i++)
	for(int j=cost[i]; j<=m; j++)
		f[j]=max(f[j],f[j-cost[i]]+value[i]);

多维背包

问题描述

多维背包对于每一个物品有多种付出的代价（如：重量，体积同时限制），仍然要求价值最大。

题解

修改一下状态定义
$f[a_1,a_2,\ldots,a_n]$分别表示$n$种付出的代价。
转移参考01背包与完全背包。

多重背包

问题描述

有$n$种物品，每个物品有三个属性：代价，价值与可选次数。给定一个载代价为$m$的背包，求可以获得的价值最大值。

题解

将每个物品拆成多个物品，保证可选次数为$1$。
对所有物品做01背包即可。
时间复杂度$O(m\sum num[i])$。

for(int i=1; i<=n; i++)
	for(int j=0; j<=m; j++)
		for(int k=0; k<=a[i]&&k*cost[i]<=j; k++)
			f[j]=max(f[j],f[j-k*cost[i]]+k*value[i]);

优化1

考虑，将一个数$x$进行二进制拆分后，$\forall y\lt x$可以用$x$的二进制拆分方式唯一表示出来。

如$13=1+2+4+6$，若选择$7=1+6$，选择$9=1+2+6$。
故我们可以对每个背包的物品进行二进制拆分，将第$i$种物品分为$O(\log num[i])$种物品，对拆分的物品代价与价值同时乘上拆分出的二进制数。

这样时间复杂度下降为$O(m\sum\log num[i])$。

void zero_one_pack(Thing a,int k) {
	a.cost*=k,a.value*=k;
	for(int j=m; j>=a.cost; j--)
		f[j]=max(f[j],f[j-a.cost]+a.value);
}

void complete_pack(const Thing& a) {
	for(int j=a.cost; j<=m; j++)
		f[j]=max(f[j],f[j-a.cost]+a.value);
}

void multiple_pack() {
	for(int i=1; i<=n; i++) {
		if(a[i].num*a[i].cost>m) { //个数太多，可视为无穷
			complete_pack(a[i]);
			continue;
		}
		int k=1;
		while(k<a[i].num) {
			zero_one_pack(a[i],k);
			a[i].num-=k;
			k<<=1;
		}
		zero_one_pack(a[i],a[i].num);
	}
}

优化2

使用单调队列优化多重背包。
重新列出转移方程。（设当前放置物品为$x$）

$$f[i]=\max_{j=0}^{num[x]} \lbrace f[i-j\cdot cost[x]]+j\cdot value[x] \rbrace$$

我们发现有个$cost[x]$非常碍眼，如果能够把$cost[x]$去掉，那么转移的编号就连续了，就可以采用各种优化方法。

考虑将方程放入$\bmod cost[x]$的剩余系中考虑（可以理解为直接将下标中$cost[x]$抹掉）。
得到方程：

$$f'[i]=\max_{j=0}^{num[x]} \lbrace f'[i-j]+j\cdot value[x] \rbrace$$ $$f'[i]=\max_{j=i-num[x]}^{i} \lbrace f'[j]+(i-j)\cdot value[x] \rbrace$$

发现在转移时，$(i-j)\cdot value[x]$是一个差的增量，因此我们可以将方程写成这样：

$$f'[i]=\max_{j=i-num[x]}^{i} \lbrace f'[j]\rbrace+i\cdot value[x]$$

此时我们就可以使用单调队列优化这个方程了。

具体实现的时候，我们需要枚举剩余系$mod$，然后进行上述Dp，注意方程中的编号$i$和实际的下标$index$不同，$index=i\cdot cost[x]+mod$，单调队列下标用$i$维护，转移时使用$index$。

时间复杂度$O(nm)$。

若可达到的价值比较小而容量可以很大，同样可以将方程对称一下，得到$O(nV)$的算法，其中$V$是最大价值。

#define pii pair<int,int>
#define mp make_pair

void trans(const Thing& a) {
	for(int mod=0; mod<a.cost; mod++) {
		deque<pii>Q;
		for(int i=0,index; (index=i*a.cost+mod)<=m; i++) {
			while(!Q.empty()&&Q.front().first<i-a.num)Q.pop_front();
			while(!Q.empty()&&Q.back().second<=f[index]-i*a.value)Q.pop_back(); //允许自己转移到自己
			Q.push_back(mp(i,f[index]-i*a.value));
			f[index]=Q.front().second+i*a.value;
		}
	}
}

void solve() {
	for(int i=1; i<=n; i++)trans(a[i]);
}

树上背包

树形依赖背包

树上有一些物品，对这一些物品做01/完全/多重背包，满足所选点形成一个连通块。

题解

不难想到使用$O(nm^2)$的算法进行暴力转移。
设$f[i,j]$表示以$i$为根的子树，容量为$j$所获得最大价值。
枚举每个儿子分配，做01/完全/多重背包。
易错点：01背包循环倒序枚举，完全背包正序枚举但要分离之前的Dp值与当前的Dp值（另开辅助数组记录）

本处以01背包举例。

void TreeDp(int Now,int fa) {
	for(int i=0; i<=m; i++)f[Now][i]=-INT_MAX/2;
	f[Now][cost[Now]]=value[Now];
	for(int Next:edges[Now]) {
		if(Next==fa)continue;
		TreeDp(Next,Now);
		for(int j=m; j>=0; j--)
			for(int k=j; k>=0; k--)
				f[Now][j]=max(f[Now][j],f[Now][j-k]+f[Next][k]);
	}
	f[Now][0]=0;
}

优化1（achen优化）

以真实结点为代价的树上背包时间复杂度是$O(n^2)$的。
即：若背包分配的代价是结点，那么严格限制转移的范围，时间复杂度是$O(n^2)$的。

注意这里的严格限制很容易漏掉限制，虽然随机数据下看似$O(n^2)$，但可以构数据卡成$O(n^3)$。
可以照着下面的程序检验是否漏掉限制。（本程序是当前状态从上一状态转移，与从当前状态转移到下一状态的写法稍有不同）

void TreeDp(int Now,int fa) {
	Size[Now]=1;
	for(int i=0; i<=n; i++)f[Now][i]=-INT_MAX/2;
	f[Now][1]=value[Now];
	for(int Next:edges[Now]) {
		if(Next==fa)continue;
		TreeDp(Next,Now);
		Size[Now]+=Size[Next];
		for(int j=Size[Now]-Size[Next]; j>=0; j--)g[j]=f[Now][j];
		for(int j=Size[Now]; j>=0; j--)
			for(int k=min(j,Size[Next]); k>=0&&j-k<=Size[Now]-Size[Next]; k--)
				f[Now][j]=max(f[Now][j],g[j-k]+f[Next][k]);
	}
	f[Now][0]=0;
}

证明：

1. 每次背包合并两棵树$T_1,T_2$的代价是$size(T_1)\cdot size(T_2)$，可以将每次合并的过程看做两棵树的结点两两配对的过程。每一对点只会在其$lca$处合并一次，故背包过程均摊是$\begin{pmatrix}n\\2\end{pmatrix}=\frac{n(n-1)}2=O(n^2)$。
2. 使用摊还分析的记账方法分析。将合并倒过来看做分解，一开始存款$\frac{n^2}2$，每一次的分解都使用存款抵付，比如将$n$分解为$x,y(x+y=n)$，$\frac{n^2}2-xy=\frac{x^2}2+\frac{y^2}2$，可见，剩余存款仍然足够抵用后序分解，当分解到只剩结点时，剩余存款为$\frac 12\times n$，故均摊时间复杂度为$\frac {n^2-n}2=O(n^2)$

当限制了背包大小为$k$时，时间复杂度可以进一步降低到$O(n\cdot\min(n,k))$，证明见这里。

优化2

对于在树上做多重背包的题目，普通算法时间复杂度是$O(nm^2)$。
此时我们可以考虑点分治。
一般的树上多重背包是从下往上更新，需要枚举转移量，因此效率低下。
经过点分治，转化为所有选择的点必须和重心连通，转化为从上往下更新。
每次向下递归时强制选择儿子，向上回溯时检查是否可以更新状态。
此时我们可以使用二进制拆分或单调队列对多重背包进行优化，将时间复杂度降为：$O(nm\log n\log d)$或$O(nm\log n)$。

模板题

非树形依赖背包

某一些题目不要求选择的物品成为连通块，同时为了利用“树”的结构，在树上作了其他限制。

题解

暴力转移类似上述依赖背包。

优化1（achen优化）

与上述achen优化相同。