0-1背包

题面

P2871

有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性。要求：选若干个物品放入背包，使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量 $W$ 。

分析

设 $f_{i,j}$ 为在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包剩余容量不变，背包中物品总价值也不变，故这种情况的最大价值为 $f_{i-1,j}$ ；当其放入背包时，背包的剩余容量会减小 $w_i$ ，背包中物品的总价值会增大 $v_i$ ，故这种情况的最大价值为 $f_{i-1,j-w_i}+v_i$ 。

由此可以得出状态转移方程：

$$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$$

这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。

由于对 $f_i$ 有影响的只有 $f_{i-1}$ ，可以去掉第一维，直接用 $f_{i}$ 来表示处理到当前物品时背包容量为 $i$ 的最大价值，得出以下方程：

$$f_j=\max(f_j,f_{j-w_i}+v_i)$$

代码

核心代码

for(int i=1;i<=n;++i)
	for(int l=W;l>=w[i];--l)
		dp[l]=max(dp[l],dp[l-w[i]]+v[i]);

例题代码

# include<iostream>
using namespace std;

const int N=3500,M=13000;
int n,m,w,d,dp[M];

int main(){
	cin>>n>>m;
	for(int i=0;i<n;++i){
		cin>>w>>d;
		for(int j=m;j>=w;--j)
			dp[j]=max(dp[j],dp[j-w]+d);
	}
	cout<<dp[m];
	return 0;
}

完全背包

题面

P1616

有 $n$ 种物品和一个容量为 $W$ 的背包，每种物品有重量 $w_i$ 和价值 $v_i$ 两种属性。要求：选若干个物品放入背包，使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量 $W$ 。

分析

设 $f_{i,j}$ 为在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。

考虑一个朴素的做法：对于第 $i$ 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 $O(n^3)$ 的。

状态转移方程如下：

$$f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k) $$

考虑做一个简单的优化。可以发现，对于 $f_{i,j}$ ，只要通过 $f_{i,j-w_i}$ 转移就可以了。因此状态转移方程为：

$$f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$$

理由是当我们这样转移时， $f_{i,j-w_i}$ 已经由 $f_{i,j-2\times w_i}$ 更新过，那么 $f_{i,j-w_i}$ 就是充分考虑了第 $i$ 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。

与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度。如果理解 0-1 背包的优化方式，就不难明白压缩后的循环是正向的。

代码

例题代码

# include<iostream>
using namespace std;
# define ll long long

const int M=1e7+5;
int m;
ll t,a,b,dp[M];

int main(){
	cin>>t>>m;
	for(int i=0;i<m;++i){
		cin>>a>>b;
		for(ll j=a;j<=t;++j)
			dp[j]=max(dp[j],dp[j-a]+b);
	}
	cout<<dp[t];
	return 0;
}

不开 long long 见祖宗

多重背包

题面

P1776

分析

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有多个，而非一个。

一个很朴素的想法就是：把「每种物品选 $k_i$ 次」等价转换为「有 $k_i$ 个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决。状态转移方程如下：

$$f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k) $$

时间复杂度 $O(W\sum_{i=1}^nk_i)$ 。

二进制分组优化

考虑优化。我们仍考虑把多重背包转化成 0-1 背包模型来求解。

解释

显然，复杂度中的 $O(nW)$ 部分无法再优化了，我们只能从 $O(\sum k_i)$ 处入手。为了表述方便，我们用 $A_{i,j}$ 代表第 $i$ 种物品拆分出的第 $j$ 个物品。

在朴素的做法中， $\forall j\le k_i$ ， $A_{i,j}$ 均表示相同物品。那么我们效率低的原因主要在于我们进行了大量重复性的工作。举例来说，我们考虑了「同时选 $A_{i,1},A_{i,2}$ 」与「同时选 $A_{i,2},A_{i,3}$ 」这两个完全等效的情况。这样的重复性工作我们进行了许多次。那么优化拆分方式就成为了解决问题的突破口。

过程

我们可以通过「二进制分组」的方式使拆分方式更加优美。

具体地说就是令 $A_{i,j}(j\in[0,\lfloor \log_2(k_i+1)\rfloor-1])$ 分别表示由 $2^j$ 个单个物品「捆绑」而成的大物品。特殊地，若 $k_i+1$ 不是 $2$ 的整数次幂，则需要在最后添加一个由 $k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}$ 个单个物品「捆绑」而成的大物品用于补足。

举两个例子：

• $18=1+2+4+8+3$
• $31=1+2+4+8+16$

显然，通过上述拆分方式，可以表示任意不大于 $k_i$ 个物品的等效选择方式。将每种物品按照上述方式拆分后，使用 0-1 背包的方法解决即可。

时间复杂度 $O(W\sum_{i=1}^n\log_2k_i)$

实现

int idx=0;
for(int i=1;i<=m;++i){
	int c=1,p,h,k;
	cin>>p>>h>>k;
	while(k>c){
		k-=c;
		list[++idx].w=c*p;
		list[idx].v=c*h;
		c*=2;
	}
	list[++idx].w=k*p;
	list[idx].v=k*h;
}

代码

例题代码

# include<iostream>
using namespace std;
# define ll long long

const int M=4e4+5;
int n,m,c;
ll W,v,w,a,b,dp[M];

int main(){
	cin>>n>>W;
	for(int i=0;i<n;++i){
		cin>>v>>w>>m;
		c=1;
		while(c<m){
			m-=c;
			a=c*v,b=c*w;
			for(ll j=W;j>=b;--j)
				dp[j]=max(dp[j],dp[j-b]+a);
			c*=2;
		}
		a=m*v,b=m*w;
		for(ll j=W;j>=b;--j)
			dp[j]=max(dp[j],dp[j-b]+a);
	}
	cout<<dp[W];
	return 0;
}

混合背包

题面

P1833

有 $n$ 种樱花树和长度为 $T$ 的时间，有的樱花树只能看一遍，有的樱花树最多看 $A_i$ 遍，有的樱花树可以看无数遍。每棵樱花树都有一个美学值 $C_{i}$ ，求在 $T$ 的时间内看哪些樱花树能使美学值最高。

分析

混合背包就是将前面三种的背包问题混合起来，这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。

实现

核心代码

for(循环物品种类){
	if(是 0 - 1 背包)
		套用 0 - 1 背包代码;
	else if(是完全背包)
		套用完全背包代码;
	else if(是多重背包)
		套用多重背包代码;
}

例题代码

# include<iostream>
# include<cstdio>
using namespace std;

const int N=1e4+5,M=1e3+5;
int h1,m1,h2,m2,t;
int n,w,v,p,c,dp[M];

void ch(int w,int v){
	for(int i=t;i>=w;--i)
		dp[i]=max(dp[i],dp[i-w]+v);
}

int main(){
	scanf("%d:%d %d:%d",&h1,&m1,&h2,&m2);
	t=(h2*60+m2)-(h1*60+m1);
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d %d",&w,&v,&p);
		if(!p)
			for(int j=w;j<=t;++j)
				dp[j]=max(dp[j],dp[j-w]+v);
		else{
			c=1;
			while(c<p){
				ch(w*c,v*c);
				p-=c,c*=2;
			}
			ch(w*p,v*p);
		}
	}
	printf("%d",dp[t]);
	return 0;
}

分组背包

题面

P1757

分析

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将 $t_{k,i}$ 表示第 $k$ 组的第 $i$ 件物品的编号是多少，再用 $\mathit{cnt}_k$ 表示第 $k$ 组物品有多少个。

实现

for(int k=1;k<=ts;k++) //循环每一组
	for(int i=m;i>=0;i--) //循环背包容量
		for (int j=1;j<=cnt[k];j++) //循环该组的每一个物品
			if(i>=w[t[k][j]]) //背包容量充足
				dp[i]=max(dp[i],dp[i-w[t[k][j]]]+c[t[k][j]]); //状态转移

这里要注意：​一定不能搞错循环顺序​，这样才能保证正确性。

有依赖的背包

题面

P1064

金明有 $n$ 元钱，想要买 $m$ 个物品，第 $i$ 件物品的价格为 $v_i$ ，重要度为 $p_i$ 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。

目标是让所有购买的物品的 $v_i \times p_i$ 之和最大。

分析

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

小优化

根据贪心原理，当费用相同时，只需保留价值最高的；当价值一定时，只需保留费用最低的；当有两件物品 $i,j$ 且 $i$ 的价值大于 $j$ 的价值并且 $i$ 的费用小于 $j$ 的费用时，只保留 $i$ 。

变式

输出方案数

输出方案其实就是记录下来背包中的某一个状态是怎么推出来的。我们可以用 $g_{i,v}$ 表示第 $i$ 件物品占用空间为 $v$ 的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略（选或不选）。

int v=V; //记录当前的存储空间

//最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for(从最后一件循环至第一件){
	if(g[i][v]){
		选了第 i 项物品;
		v-=第 i 项物品的重量;
	}
	else
		未选第 i 项物品;
}

求最优方案数

对于给定的一个背包容量、物品费用、其他关系等的问题，求装到一定容量的方案总数。

这种问题就是把求最大值换成求和即可。

例如 0-1 背包问题的转移方程就变成了：

$$\mathit{dp}_i=\sum(\mathit{dp}_i,\mathit{dp}_{i-c_i}) $$

初始条件： $\mathit{dp}_0=1$

因为当容量为 $0$ 时也有一个方案，即什么都不装。

A1273 货币系统

# include<iostream>
using namespace std;

const int M=1e5+5,N=1e3+5;
int m,n,w;
long long dp[M];

int main(){
	cin>>n>>m;
	dp[0]=1;
	for(int i=1;i<=n;++i){
		cin>>w;
		for(int j=w;j<=m;++j)
			dp[j]+=dp[j-w];
	}
	cout<<dp[m];
	return 0;
}