背包DP

背包DP是 DP 中最基础的一种，比较好理解的，接下来介绍几种背包DP。

首先要了解背包DP解决的问题，就是类似于求给定一个可取价值和一些物品数量和单个价值，在各种约束下可以达到的最值。

01背包

属于最基础的了，但是其他背包基本都要建立在它身上。

01背包就是有 $n$ 物品，每个物品有它的价值 $v_i$ 和重量 $w_i$ ，你可以选总容量为 $W$ 的物品，但是每件物品只能选一件，求最大价值。

我们设 $f_{i,j}$ 表示选前 $i$ 个物品，最大容量为 $j$ 的最大价值。这个数组的转移显然是 $f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$ 满足 $w_i\le j$ 。这个转移了，求最大的两个数 $f_{i-1,j}$ 和 $f_{i-1,j-w_i}+v_i$ 分别是当前位置不取，取上一个位的值，和当前位置取，所以价值要减去 $w_i$ ，这里省略使用表格来理解的过程。答案显然是 $f_{n,W}$ 。

这个转移是时间复杂度是 $O(nW)$ ，是优秀的，但是空间复杂度 $O(nW)$ 对比起来就是 shit。考虑滚动数组优化空间。

设 $f_j$ 表示前 $j$ 的物品的最大价值。转移其实和二维的一样，是 $f_j=\max(f_j,f_{j-w_i}+v_i)$ 且满足 $w_i\le j$ 。在此处，可以省略掉第一位的原因就是因为第 $i$ 个数据只受 $i-1$ 的影响，所以可以滚动优化。但是注意滚动优化的时候，第二层循环要从大至小遍历，不然的话有一些数据会多取几次。因为是一维且从大到小，只有从 $W$ 循环到 $w_i$ 即可。当然滚动数组也可以用两个数组来进行交换实现。答案显然是 $f_W$ 。

空间复杂度 $O(W)$ 。

注意点 1.注意如果用二维的，第二次循环是有从小到大，而滚动数组的是从大到小 2.注意滚动是答案是 $f_W$ ，不要写成 $f_n$ 。 3.用二维数组的时候不要直接从 $w_i$ 遍历的 $W$ ，因为它是从小到大循环的。 4. $f$ 数组的大小要开 $\max W$ 。

code

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int w[N],v[N];
int W,n;
int dp[20010];
int main(){
	cin>>W>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=W;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
	return 0;
}

完全背包

完全背包就是有 $n$ 物品，每个物品有它的价值 $v_i$ 和重量 $w_i$ ，你可以选总容量为 $W$ 的物品，每件物品可以拿任意次，求最大价值。

完全背包和01背包的区别就在于可以取多次。

这里只讲述滚动优化的，朴素的以后在补。

设 $f_j$ 表示前 $j$ 的物品的最大价值。转移： $f_j=\max(f_j,f_{j-w_i}+v_i)$ 且满足 $w_i\le j$ 。这时你会发现：这个东西不是和01背包的长得完全一样吗？确实是。但是，不同点就在于怎么遍历取更新这一个 $f$ 数组。在01背包中，我们说了，01背包的第二层循环要倒序遍历，因为正序遍历有一些数据会多计算，而这正好符合了完全背包的做法，所以只需要将循环从 $w_i$ 到 $W$ 即可。

时间复杂度 $O(nW)$ ，空间复杂度 $O(W)$ 。 注意点 注意要正序遍历。其他同01背包。

code

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int w[N],v[N];
int W,n;
int dp[20010];
int main(){
	cin>>W>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=W;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
	return 0;
}

多重背包

多重背包就是有 $n$ 物品，每个物品有价值 $v_i$ 和重量 $w_i$ ，还有数量 $s_i$ ，你可以选总容量为 $W$ 的物品，每件物品最多可以拿 $s_i$ 个，求最大价值。

先考虑朴素做法。

发现这一个问题可以拆成多个01背包来解决，就是把第 $i$ 种物品拆分成 $c_i$ 种只有一个的物品的01背包去做。

时间复杂度貌似是枚举每一个重量的和拆01背包的 $O(V\sum c_i)$ 。

太慢了，考虑优化。

使用二进制分组优化，因为每一个正整数都可以表示为一个二进制，我们可以反推过来，用 $\log n$ 个二进制表示从 $0$ 到 $c_i$ 的任何数，将 $c_i$ 是用二进制拆分，得到的结果去算贡献替换掉 $w_i$ 和 $v_i$ 中的值，就可以做到很快的速度处理多重背包了。

时间复杂度 $O(nm\log V)$ 。

还有一种使用单调队列优化的空间 $O(nm)$ 的做法，等我学了再写。

注意点 1.注意二进制分组的剩余的值要特殊处理。

code

朴素做法：

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=10100;
int w[N],v[N],s[N];
int W,n;
int dp[N];
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>s[i];
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=s[k];i++){
			for(int j=W;j>=w[k];j--){
				dp[j]=max(dp[j],dp[j-w[k]]+v[k]);
			}
		}
	}
	cout<<dp[W];
	return 0;
}

二进制优化：

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int w[N],v[N],s[N];
int W,n;
int dp[N];
int cnt;
int vi,wi,si;
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		cin>>wi>>vi>>si;
		int k=1;
		while(k<=si){
			cnt++;
			w[cnt]=wi*k;
			v[cnt]=vi*k;
			si-=k;
			k*=2;
		}
		if(si){
			cnt++;
			w[cnt]=wi*si;
			v[cnt]=vi*si;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=W;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
	return 0;
}

分组背包

分组背包就是有 $n$ 组物品，每组物品有 $s_i$ 个，第 $s_i$ 里的第 $j$ 个物品有价值 $v_{i,j}$ 和重量 $w_{i,j}$ ，每组至多可以拿一个，求在可以拿 $W$ 个的情况下的最大价值。

发现本题可以直接把每组拆成01背包去做，每一次在里面多跑一个 $s_i$ 组的东西，然后直接模版就行了，

时间复杂度貌似是 $O(nV\max s_i)$ ，空间复杂度貌似是 $O(V+n\max s_i)$ 。

注意点 1.注意跑01背包时的转换模板中的 $v_i$ 和 $w_i$ 。

code

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N][N],w[N][N],s[N];
int dp[N];
int n,W;
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		for(int j=1;j<=s[i];j++){
			cin>>v[i][j]>>w[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=W;j>=0;j--){
			for(int k=1;k<=s[i];k++){
				if(j>=v[i][k]){
					dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
				}
			}
		}
	}
	cout<<dp[W];
	return 0;
}

01背包

code

完全背包

code

多重背包

code

分组背包

code

文章留言区

发表您的见解