五类背包问题总结笔记 | Bill Yang's Blog
0%

五类背包问题总结笔记

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

01背包

问题描述

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

题解

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

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

1
2
3
4
5
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

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

1
2
3
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。

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

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

完全背包

问题描述

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

题解

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

优化

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

1
2
3
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])$。

1
2
3
4
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])$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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$)

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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背包举例。

1
2
3
4
5
6
7
8
9
10
11
12
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)$。
可以照着下面的程序检验是否漏掉限制。(本程序是当前状态从上一状态转移,与从当前状态转移到下一状态的写法稍有不同)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

优化2

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

模板题

非树形依赖背包

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

题解

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

优化1(achen优化)

与上述achen优化相同。

姥爷们赏瓶冰阔落吧~