第五章 动态规划（一）

一、背包问题

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

1.01背包问题

01背包问题特点：每种物品仅有一件

状态表示：定义\(f(i,j)\)表示只从前\(i\)个物品中选择，总体积不超过\(j\)的最大价值，最终答案为\(f(n,m)\)

状态转移：\(f(i,j)\)可以分为不选物品\(i\)和选物品\(i\)两种情况

状态转移方程:

\[f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i) \]

int f[N][N];
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		f[i][j]=f[i-1][j];
		if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
	}
}

优化：从二维变成一维

int f[N];
//j从大到小遍历，保证f[j]在f[j-v[i]]改变前改变，从而使当前的f[j-v[i]]表示i-1时的状态
for(int i=1;i<=n;i++)
	for(int j=m;j>=v[i];j++)
		f[j]=max(f[j],f[j-v[i]]+w[i]);

2.完全背包问题

完全背包问题特点：每种物品有无数件

思路：类比01背包

状态表示：定义\(f(i,j)\)表示只从前\(i\)个物品中选择，总体积不超过\(j\)的最大价值

状态转移：\(f(i,j)\)可以分为不选物品\(i\)和选\(1\) ~ \(\lfloor\frac{j}{v_i}\rfloor\)个物品\(i\)两种情况

等价变形：\(f(i,j)\)可以分为选\(0\) ~ \(\lfloor\frac{j}{v_i}\rfloor\)个物品\(i\)的情况

状态转移方程:

\[f(i,j)=max(f(i,j),f(i-1,j-kv_i)+kw_i)\quad(k\in [0,\lfloor\frac{j}{v_i}\rfloor],k\in Z) \]

int f[N][N];
for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		for(int k=0;k*v[i]<=j;k++)
			f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

优化：对于\(f(i,j)\)和\(f(i,j-v_i)\)而言：

\(f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i,f(i-1,j-2v_i)+2w_i,\cdots)\)

\(f(i,j-v_i)=max(f(i-1,j-v_i),f(i-1,j-2v_i)+w_i,f(i-1,j-3v_i)+2w_i,\cdots)\)

我们惊奇的发现：\(f(i,j-v_i)\)的表达式与\(f(i,j)\)的表达式除第一项以外只差\(w_i\)

于是将状态转移方程改写为：

\[f(i,j)=max(f(i-1,j),f(i,j-v_i)+w_i) \]

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

再优化：从二维变成一维

int f[N];
for(int i=1;i<=n;i++)
	for(int j=v[i];j<=m;j++)
		f[j]=max(f[j],f[j-v[i]]+w[i]);

3.多重背包问题

多重背包问题特点：每种物品有件数限制

额外定义物品\(i\)有\(s_i\)件

状态表示：定义\(f(i,j)\)表示只从前\(i\)个物品中选择，总体积不超过\(j\)的最大价值

状态转移：\(f(i,j)\)可以分为选\(0\) ~ \(min(s_i,\lfloor\frac{j}{v_i}\rfloor)\)个物品\(i\)的情况

状态转移方程:

\[f(i,j)=max(f(i,j),f(i-1,j-kv_i)+kw_i)\quad(k\in [0,min(s_i,\lfloor\frac{j}{v_i}\rfloor)],k\in Z) \]

时间复杂度：\(O(nms)\)

for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
			f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

优化：转化为01背包问题

假设物品\(i\)有\(1000\)件，则可以选择的数量有\(0,1,2,\cdots,1000\)，我们将物品按\(1,2,4,\cdots,256,489(\)此处为\(1000-511)\)件进行“打包”，则可将问题转化为“打包”后新\(\log n\)个物品的01背包问题，时间复杂度 \(O(nms)\)变为\(O(nm\log s)\)

//这里注意 N 至少要开到 n * logs (基佬紫警告
int v[N],w[N];
int f[N];
int n,m,cnt;
//边读边打包
for(int i=1;i<=n;i++){
	int a,b,s;
	scanf("%d%d%d",&a,&b,&s);
	//打包存储，cnt记录打包后物品总数量 
	int k=1;
	while(k<=s){
		cnt++;
		v[cnt]=a*k;
		w[cnt]=b*k;
		s-=k;
		k*=2;
	}
	//剩余不足 2 的更高次幂个物品额外打包 
	if(s>0){
		cnt++;
		v[cnt]=a*s;
		w[cnt]=b*s;
	}
} 
//物品个数为cnt，背包容量为m的01背包问题模板
for(int i=1;i<=cnt;i++)
	for(int j=m;j>=v[i];j--)
		f[j]=max(f[j],f[j-v[i]]+w[i]);

4.分组背包问题

分组背包问题特点：物品分为多组，每组内有若干个，每组只能选一个

状态表示：定义\(f(i,j)\)表示只从前\(i\)组物品中选择，总体积不超过\(j\)的最大价值

状态转移：\(f(i,j)\)可以分为不从第\(i\)组物品中选和从第\(i\)组物品中选第\(k\)个物品两种情况

状态转移方程：

\[f(i,j)=max(f(i-1,j),f(i-1,j-v_{(i,k)})+w_{(i,k)}) \]

优化：从二维变成一维（类比01背包，\(j\)从大到小遍历）

int n,m;//n组物品，容量为m
int v[N][N],w[N][N],s[N];//s[i]表示第i组物品的件数
int f[N];
for(int i=1;i<=n;i++)
	for(int j=m;j>=0;j--)
		for(int k=1;k<=s[i];k++)
			if(v[i][k]<=j)
				f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);