【学习笔记】 背包问题

1. \(01\) 背包

Q：有 \(N\) 件物品和一个容量为 \(V\) 的背包。第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。求解将哪些物品装入背包可使价值总和最大。

规定：\(f_{i,j}\) 表示前 \(i\) 件物品放入容量为 \(j\) 的背包可以获得的最大价值，所以

\[\large{f_{i,j}=\max_{i\in [1,N],j\in [v_i,V]}(f_{i-1,j},f_{i-1,j-v_i}+w_i)}\]

在此基础上，还可以降维打击，考虑将 \(f\) 第一维去掉，此时 \(f_j=\max(f_j,f_{j-v_i}+w_i)\)，但此时我们需要将内层循环 \(j\) 逆序循环。

代码：

For i=1..N
	For j=V..v[i]
		f[j]=max{f[j],f[j-v[i]]+w[i]};
result: f[V]

为什么逆序 ？

对比上面的递推式， \(f_j\) 为第 \(i\) 时刻的 \(f_j\)，\(f_{j-v_i}\) 为第 \(i-1\) 时刻的 \(f_{j-v_i}\)。

当外层循环执行到 \(i\)，内层循环还没开始执行时， \(f_{j-v_i}\) 为 \(i-1\) 时刻的。

我们要保留这个 \(i-1\) 时刻的 \(f_{j-v_i}\)，就要 \(i-1\) 时刻的 \(f_j\) 在 \(f_{j-v_i}\) 更新前率先更新为 \(i\) 时刻的 \(f_j\) ，即在 \(j-v_i\) 前更新 \(j\)，所以逆序循环。

2. 完全背包

Q：在 01 背包的基础上规定每个物品可用无限次，求最大价值。

一个朴素的方法是用多一重循环 \(k\) 记录每个物品所用的数量，状态转移：

\[\large{f_{i,j}=\max_{k\times v_i\in [0,j]}(f_{i-1,j},f_{i-1,j-k\times v_i}+k\times w_i)}\]

不过时间复杂度较大，于是就诞生了一个巧妙的方法：把完全背包转化为 01 背包求解。

首先我们要知道，任何一个数都可以通过 2 的幂次方数表示，如 \(11=2^3+2^1+2^0\)，并且每一个幂次方数都能够仅出现一次。

然后我们发现，一个体积为 \(V\) 的背包中最多能装下 \(\left \lfloor \dfrac {V}{v_i}\right \rfloor\) 个体积为 \(v_i\) 的物品。每一种物品数量是有限的，这意味着我们可以把每一种物品拆分。

具体的说，可以把第 \(i\) 种物品拆成体积为 \(v_i\times 2^k\)，价值为 \(w_i\times 2^k\) 的若干件物品，其中 \(v_i\times 2^k\leq V,k\in Z\)。

如此时间复杂度降为 \(O(N\times \sum log \dfrac {V}{v_i})\)。

但我们还是不想扩大时间复杂度，所以仍然有一个 \(O(NV)\) 的解决方法：将 01 背包中的内层循环由逆序再改回正序。

代码：

For i=1..N
	For j=v[i]..V
		f[j]=max(f[j],f[j-v[i]]+w[i]);
result: f[V]

为什么正序可以满足题意 ？

反过来想 01 背包为什么要逆序？因为 \(i\) 时刻的 \(f_j\) 需要 \(i-1\) 时刻的 \(f_{j-v_i}\) 更新，所以在第 \(i\) 时刻时 \(f_j\) 要率先被遍历到。

换句话说，这是为了保证递推唯一，即每件物品只选一次。

而完全背包恰好相反，或许确实需要那个可能选入第 \(i\) 件物品的结果，即第 \(i\) 时刻的 \(f_{j-v_i}\)，因此采用顺序循环便是最简单的解决方式。

3.多重背包

Q：在 01 背包的基础上规定第 \(i\) 件物品最多有 \(s_i\) 件，求最大价值。

很容易想到把 \(s_i\) 件物品全部拆分，转化为 01 背包问题，但如果每种物品限定数量很多，时间复杂度就过大。

于是我们想到了上面完全背包用2的幂次方数拆分的二进制拆分法，但要稍加改动：

假设 \(s=13\) ，在 \(0\sim13\) 中选一个数，例如 \(11\)，我们需要拆分出 \(2^0,2^1,2^2,2^3\)，然后选出 \(2^0,2^1,2^3\) 来组成。

但程序可以组出 \(2^0+2^1+2^2+2^3=15\) 这样大于 \(s=13\) 的数，不符合限制。

所以正确的做法是：保证拆分出的 \(2\) 的幂次方数之和始终不大于 \(s\)，余下部分通过相减来补齐。

\(e.g.\text{ } 13\) 可以拆分出 \(2^0,2^1,2^2\) 和 \(13-2^0-2^1-2^2=6\)，即 \(1,2,4,6\)。

代码：（vector Q 存储拆分出物品的体积和价值）

For i=1..N
{
	k=1;
	While k<=s[i] do
	{
		s[i]-=k;
		Q.pushback({v[i]*k,w[i]*k});
		k<<=1; //指数+1
	}
	If(s>0) Q.pushback({v[i]*s,w[i]*s});
}
For auto Q
	For j=V..Q.v
		f[j]=max(f[j],f[j-Q.v]+Q.w);
result: f[V]

单调队列优化 \(O(NV)\)

试写出多重背包的朴素转移：

\[\large{f_{i,j}=\max(f_{i-1,j},f_{i-1,j-k\times v_i}+k\times w_i)}\]

其中 \(k\in[ 1,min(\left \lfloor \dfrac {V}{v_i} \right \rfloor,s_i) ]\)，仿照 01 背包的想法，考虑 \(f_{i,j}\) 对其它状态的影响：

我们发现如果往体积为 \(j-(k+1)\times v_i\) 的背包中填充体积为 \(v_i\) 的物品，体积变化为 \(j-k\times v_i\)。

归纳来看，\(f_{i,j}\) 会影响 \(f_{i,j+k\times v_i}\)（\(j+k\times v_i \leq V\)。

那么，\(j+k\times v_i\) 能联想到什么？是等差数列，并且公差就是 \(v_i\) ，举个例子：

图中每一种颜色构成的数列均为公差为 \(v_i=4\) 的等差数列，意味着同一种颜色的格子对 \(v_i\) 取模得到的余数相同。

即通项公式为 \(j=k\times v_i+取模得到的余数\)，所以我们可以通过取模得到的余数分出 \(0,1,2,..,v_i-1\) 共 \(v_i\) 组，

令公差为 \(d=v_i\)，全选状态下物品个数 \(a=\left \lfloor \dfrac {j}{v_i} \right \rfloor\)，余数 \(b=j \% v_i\)，所以写成 \(j=a\times d+b\)，带回得：

\[\normalsize{j-k\times d=a\times d+b-k\times d=(a-k)\times d+b}\]

回想转移方程中 \(f_{i,j-k\times v_i}+k\times w_i\) 代表选择 \(k\) 件第 \(i\) 种物品，全选是 \(a\)，所以不选择 \(a-k\) 件物品。

如果令 \(a-k=k'\)，则状态变成：

\[\large{f_{i,j}=max(f_{i-1,k'\times d+b}+a\times w_i-k'\times w_i )}\]

其中 \(a\times w_i\) 为常量，将其从 \(max\) 中移出。则：

\[\large{f_{i,j}=max(f_{i-1,k'\times d+b}-k'\times w_i )+a\times w_i}\]

如果把 \(f_{i,j}\) 之前所有的 $f_{i-1,k'd+b}-k'w_i $ 放入一个队列，答案转化为求这个最长为 \(min(\left \lfloor \dfrac {V}{v_i} \right \rfloor,s_i)+1\) 的队列的最大值+ \(a\times w_i\)。

所以考虑单调队列优化。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1000010;
struct Mylist {
	int val,pos;
}que[N];
int n,V,head,tail,f[N],c[N],w[N],num[N];
int main(){
	scanf("%d%d",&n,&V);
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d",&w[i],&c[i],&num[i]); //c[i]代表体积，w[i]代表价值，num[i]代表数量 
		if(V/c[i]<num[i]) {
			num[i]=V/c[i];
		}
		for(int mo=0;mo<c[i];mo++) {
			head=tail=0;
			for(int k=0;k<=(V-mo)/c[i];k++) {
				int x=k;
				int y=f[k*c[i]+mo]-k*w[i];
				while(head<tail && que[head].pos<k-num[i]) head++;
				while(head<tail && que[tail-1].val<=y)tail--;
				que[tail].pos=x;
				que[tail].val=y;
				tail++; 
				f[k*c[i]+mo]=que[head].val+k*w[i];
			}
		}
	}
	printf("%d\n",f[V]);
	return 0;
}

4.混合背包

Q：有些物品只能放一次，有些物品可以放无限次，有些物品可以放 \(s_i\) 次，求最大价值。

其实就是上面三中背包合在一起。

把可以放 \(s_i\) 次的二进制拆分，当作 01 背包，和只能放一次的倒序循环处理。

然后把可以放无限次的正序循环处理就行了。

5.二维费用背包

Q：在 01 背包基础上，每件物品都有一个重量 \(m_i\)，要求所选物品还要满足总重量不超过背包核载 \(M\)，求最大价值。

其实感觉就像两个 01 背包，一个限制体积，一个限制重量，事实上也差不多（多定义一维）。

\(f_{i,j}\) 表示背包体积为 \(i\)，重量为 \(j\) 时的最大价值。相同地：

\[\large{f_{j,k}=max(f_{j,k},f_{j-v_i,k-m_i}+w_i)}\]

所以内层两个循环都是逆序循环。

代码：

For i=1..N
	For j=V..v[i]
		For k=M..m[i]
			f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
result: f[V][M]

6.分组背包

Q：有 \(N\) 组物品和容量为 \(V\) 的背包，每一组内最多只能选一个物品，求最大价值。

和多重背包问题很像，多重背包是考虑选多少个物品，分组背包是考虑每一组选哪个物品。

对每一组的 \(n\) 个物品有 \(n+1\) 种方案，即不选，选第一个，选第二个...以此类推。多一重循环枚举即可。

代码：

For i=1..N
{
	read n;
	For j=1..n 
		read v[j],w[j];
	For j=V..0
		For k=0..n
			if(j>=v[k]) f[j]=max(f[j],f[j-v[k]]+w[k]);
}
result: f[V];

7.树形依赖背包

Q：有 \(N\) 件物品和容量为 \(V\) 的背包。物品间形成依赖关系，且依赖关系组成一棵树。如果选择一个物品，则必须选择它的父节点。 其中每个物品有体积 \(v_i\)，价值 \(w_i\)，和所依赖的父节点编号 \(p_i\)，求最大价值。

对于一棵树，如何去表示状态？普通的背包用 \(f_i\) 表示体积为 \(i\) 时的最大价值，但放到一棵树中，为了定位到我们需要选的一个子树，还需要记录根节点。

定义 \(f_{i,j}\) 表示以 \(i\) 为根节点并包含 \(i\) 的一棵子树，当体积为 \(j\) 时的最大价值。试着写出状态转移：

\[\large{f_{x,j}=\max(f_{x,j},f_{x,j-k}+f_{son,k})_{(x为当前节点，son为儿子节点)}}\]

整个过程是递归到叶子节点再自下向上的。

代码：

void dfs(int x)
{
    f[x][1]=a[x];
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        dfs(y);
        for(int j=m+1;j>=1;--j)
            for(int k=1;k<j;++k)
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
    }
}

看上去很不错，但还可以上下界优化，优化之后被严格证明为 \(O(NV)\)。

void dfs(int x)
{
    siz[x]=1;
    f[x][1]=a[x];
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        dfs(y);
        for(int j=min(m+1,siz[x]+siz[y]);j>=1;--j)
            for(int k=max(1,j-siz[x]);k<=min(siz[y],j);++k)
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
        siz[x]+=siz[y];
    }
}

相比自下向上的 dp，可以转变思路：对于一个节点，分为选和不选。假定选这个节点，往下递归，最后和不选的进行比较。

代码：

void dp(int x,int m,int fa)
{//当前节点编号，背包剩余体积，父节点编号 
	if(m<=0)return;
	for(int i=head[x];i;i=next[i])
	{
		int y=ver[i];
		if(y==fa)continue;
		for(int k=0;k<=m;++k)
        	f[y][k]=f[x][k]+v[y];//选 
		dp(y,m-p[y],x);//由上至下 
		for(int k=p[y];k<=m;++k)
            f[x][k]=max(f[x][k],f[y][k-p[y]]);//和不选的比较，留取最大值 
	}
}

复杂度为 \(O(NV)\)。

8.泛化物品背包

9-1.背包最优方案总数

一个可行的方案是：用 \(g_i\) 表示背包容量为 \(i\) 时的方案数，然后常规背包得出最优解，遍历\(f_i\)，若和最优解相同，答案就加上 \(g_i\)。

那么如何预处理出 \(g_i\) ？只要确定状态转移时来自哪一种决策即可。

代码：

g[0]=1;f[1..V]=-INF;//当背包容量为0时只有“不选”这1种方案
For i=1..N
	For j=V..v[i]
	{
		int tmp_f,tmp_g;
		tmp_f=max(f[j],f[j-v[i]]+w[i]);
		tmp_f==f[j] ? tmp+=g[j] : tmp+=g[j-v[i]] ;//判断来自哪一种决策，注意方案数不需要加w[i];
		f[j]=tmp_f;
		g[j]=tmp_g;
	}
int maxw=0,ans=0;
For i=0..V  maxw=max(maxw,f[i]);
For i=0..V
	if(maxw==f[i])ans+=g[i];
result: ans

为什么 \(f_{1..V}\) 要预处理成极小值？为什么最优解不是 \(f[m]\) 了 ？

因为要统计 \(g_i\)，这里的 \(f_i\) 的意义并不是背包容量为 \(i\) 时的最大价值，而是背包容量恰好为 \(i\) 时的最大价值，因此最优解并不是 \(f[m]\)。

为了达成恰好为 \(i\) 的目的，\(f_{1..V}\) 应赋值为极小值，原因见下文。

9-2.背包具体方案

和求方案总数一样，需要确定状态转移时来自哪一种决策，在此用 \(g_{i,j}\) 记录。

由于 \(f_{i,j}=f_{i-1,j}\) 表示不选第 \(i\) 件物品，令 \(g_{i,j}=0\)。反之，若 \(f_{i,j}=f_{i-1,j-v_i}+w_i\)，则令 \(g_{i,j}=1\)。

最后从后往前用 \(g_{i,j}\) 来判断是否选择了该物品即可。

不过既然需要记录物品和容量，\(g\) 数组只能是二维，但 \(f\) 数组仍可保留一维。

代码：

For i=1..N
	For j=V..v[i]
	{
		f[j]=max(f[j],f[j-v[i]]+w[i]);
		if(f[j]==f[j-v[i]]+w[i])g[i][j]=1;
	}
int i=N,lf=V;
while(i>0)
{
	if(g[i][lf])
		printf("%d ",i),lf-=v[i];
	i--;
}

注：此时输出的物品选择方案是降序的。

9-3.背包k优解

10.背包状态与初始化

背包恰好装满：\(f[0]=0\)，\(f[1\sim V]=-inf\)。

背包不要求恰好装满：\(f[0\sim V]=0\)。

为什么 ？

初始化的 \(f\) 数组实际就是在没有任何物品可以放入背包时的合法状态，或者说初始化 \(f[i]=0\) 代表最后还剩 \(i\) 的体积是合法的。

参考链接：

https://www.cnblogs.com/jbelial/articles/2116074.html 《dd大牛的背包九讲》

https://www.bilibili.com/video/BV1qt411Z7nE 闫学灿'背包九讲专题'

https://www.luogu.com.cn/blog/RPdreamer/bei-bao-wen-ti 洛谷日报#61 背包问题

https://oi-wiki.org/dp/knapsack/ OIwiki 背包dp