背包总结

这是一篇背包类问题的博客

01 背包

性质：有一堆物品可以随便取，但每件物品$\color{red}只能拿一次$，求能拿到的价值最大为多少。

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int V,N,v[1000+10],w[1000+10],dp[1000+10];
int main(){
	ios::sync_with_stdio(false);
	cin>>N>>V;
   	//输入
	for(int i=1;i<=N;++i){
		cin>>v[i]>>w[i];
	}
    //输入
	for(int i=1;i<=N;i++){
  	//枚举重量
		for(int j=V;j>=v[i];j--){
        	//倒序枚举
			if(dp[j-v[i]]+w[i]>dp[j]) dp[j]=dp[j-v[i]]+w[i];
            //状态转移方程
		}
	}
	cout<<dp[V]<<endl;
    //完美地结束
	return 0;
}

代码解释：

$\color{purple}V$表示背包的容积（最多可以装的代价之和）

$\color{purple}N$表示物品件数

$\color{purple}v[i]$表示第$i$件物品的重量（代价）

$\color{purple}w[i]$表示第$i$件物品的价值

$\color{purple}dp[i]$ 表示在$i$重量内可以拿到的最大价值

时间复杂度：$O(N\times V)$

空间复杂度：$O(V)$

完全背包（或无限背包）

性质：有一堆物品可以随便取，但每件物品$\color{red}可以随便拿$，求能拿到的价值最大为多少。

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int m,n,v[1000+10],w[1000+10],dp[1000+10];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	//输入 
	for(int i=1;i<=n;++i){
		cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		//顺序枚举 
		for(int j=v[i];j<=m;j++){
			//重要 ：顺序枚举 
			if(dp[j-v[i]]+w[i]>dp[j]) dp[j]=dp[j-v[i]]+w[i];
			//状态转移方程 
		}
	}
	cout<<dp[m]<<endl;
	//完美地结束 
	return 0;
}

代码解释：

$\color{blue}m$表示背包的容积（最多可以装的代价之和）

$\color{blue}n$表示物品件数

$\color{blue}v[i]$表示第$i$件物品的重量（代价）

$\color{blue}w[i]$表示第$i$件物品的价值

$\color{blue}dp[i]$ 表示在$i$重量内可以拿到的最大价值

时间复杂度：$O(n\times m)$

空间复杂度：$O(m)$

多重背包

性质：有一堆物品可以随便取，但每件物品$\color{red}有拿的次数上限$，求能拿到的价值最大为多少。

模板：

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
27
28
29
#include<bits/stdc++.h>
using namespace std;
int v[600000+10],w[600000+10];
int dp[600000+10],n,m,n1;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x,y,s,t=1;
		cin>>x>>y>>s;
		//输入 
		while(s>=t){ //二进制分堆 
			v[++n1]=x*t;
			w[n1]=y*t;
			s-=t;t*=2;
		}
		v[++n1]=x*s;
		w[n1]=y*s;
	}
	for(int i=1;i<=n1;i++){
		for(int j=m;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
			//统计 
		}
	}
	cout<<dp[m]<<endl;
	//完美的结束 
	return 0;
}

代码解释：

$\color{brown}m$表示背包的容积（最多可以装的代价之和）

$\color{brown}n$表示物品件数

$\color{brown}v[i]$表示第$i$件物品的重量（代价）

$\color{brown}w[i]$表示第$i$件物品的价值

$\color{brown}dp[i]$ 表示在$i$重量内可以拿到的最大价值

这里头使用了二进制优化，优化有效，证明如下：

要证明多重背包问题的二进制优化是有效的，可以通过对比$\color{pink}证明其与原问题的解是等价的，且时间复杂度更低$。

二进制优化是将多重背包问题转化为0-1背包问题，具体过程如下：

  1. 对于每个物品i，将其拆分为若干个不同重量的0-1背包物品，拆分的原则是采用二进制思想，将物品i拆分为重量为2^k * w[i]的若干个物品（即2的幂次倍）。
    例如，如果物品i的重量w[i]为4，那么拆分为重量为4、8、16、32……的物品。

  2. 将拆分后的物品视为0-1背包问题中的普通物品，即每个物品只能选择放入一次。

为了证明二进制优化是有效的，需要证明在使用二进制优化后，所求得的最大价值与原问题的最大价值是相等的。

证明过程如下：

首先考虑原问题的最优解，设其最优解为opt1，每个物品的选择情况为$x_1, x_2, …, x_n$。其中$x_i$表示第i个物品的选择数量。

然后考虑二进制优化后的问题的最优解，设其最优解为opt2，每个物品的选择情况为$y_1, y_2, …, y_n’$。其中$y_n’$表示第n个物品（拆分后）的选择数量。

在拆分后的问题中，由于每个物品只能选择放入一次，因此拆分后的最优解满足以下条件：
$y_1 \times (2^{k1} \times w[1]) + y2 \times (2^{k2} \times w[2]) + … + yn’ \times (2^{kn’} \times w[n]) <= m$，
其中m表示背包的容量。

由于拆分后的物品覆盖了原问题中所有可能的选择情况，即每个选项都能够用拆分后的物品选择数量的和表示，因此有：
$x_1 \times v[1] + x_2 \times v[2] + … + x_n \times v[n] = y_1 \times (2^{k1} \times v[1]) + y_2 \times (2^{k2} \times v[2]) + … + y_n’ \times (2^{kn’} \times v[n])$，
其中$v_i$表示第$i$个物品的价值。

综上所述，拆分后的问题最优解opt2的价值与原问题的最优解opt1的$\color{red}价值是相等的$。

另外，使用二进制优化后，由于物品数量取决于拆分后每个物品的选择数量，而每个物品的选择数量最多只有log(m/w[i])个（其中w[i]表示第i个物品的重量），因此使用二进制优化后的算法时间复杂度更低，可以达到$O(n*\log{(m/w[i])})$。

综上所述，多重背包问题的二进制优化是有效的。

时间复杂度：$O(n \times \log(t) \times \log(m))$

空间复杂度：$O(m)$

混合背包

性质：有一堆物品可以随便取，但每件物品$\color{red}拿的次数有或没有上限$，求能拿到的价值最大为多少。

模板：

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
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int m,n,w[1000+10],c[1000+10],p[1000+10],f[1000000+10];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>p[i];
	//输入 
	for(int i=1;i<=n;i++){
		if(p[i]==0){
			//无限背包 
			for(int j=w[i];j<=m;j++){
				f[j]=max(f[j],f[j-w[i]]+c[i]);
			}
		}
		else{
			//01背包或多重背包 
			p[i]=abs(p[i]);
			for(int k=1;k<=p[i];k++){
				for(int j=m;j>=w[i];j--){
					f[j]=max(f[j],f[j-w[i]]+c[i]);
				} 
			}
			//或者写二进制优化 
		}
	}
	cout<<f[m]<<endl;
	//完美地结束 
	return 0;
}

代码解释：

$\color{orange}m$表示背包的容积（最多可以装的代价之和）

$\color{orange}n$表示物品件数

$\color{orange}w[i]$表示第$i$件物品的重量（代价）

$\color{orange}c[i]$表示第$i$件物品的价值

$\color{orange}p[i]$表示第$i$件物品可以去取得次数上限（为零则可取无限次）

$\color{orange}f[i]$ 表示在$i$重量内可以拿到的最大价值

时间复杂度：$O(n \times \log(t) \times \log(m))$

空间复杂度：$O(m)$

分组背包

性质：每组物品有若干个，同一组内的物品$\color{red}最多只能选一个$。

模板：

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
#include<bits/stdc++.h>
using namespace std;
int v,n,t=0,w[1000+10],c[1000+10],a[100+10][100000+10],f[1000000];
int main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		int p;
		cin>>w[i]>>c[i]>>p;
		a[p][++a[p][0]]=i;
		t=max(p,t);
	}
	for(int p=1;p<=t;p++){
		for(int j=v;j>=0;j--){
			for(int i=1;i<=a[p][0];i++){
				if(j>=w[a[p][i]]){
					int tmp=a[p][i];
					if(f[j]<f[j-w[tmp]]+c[tmp]){
						f[j]=f[j-w[tmp]]+c[tmp];
					}
				}
			}
		}
	}
	cout<<f[v]<<endl;
	return 0;
}

代码解释：

$\color{lightgrey}v$表示背包的容积（最多可以装的代价之和）

$\color{lightgrey}n$表示物品件数

$\color{lightgrey}w[i]$表示第$i$件物品的重量（代价）

$\color{lightgrey}c[i]$表示第$i$件物品的价值

$\color{lightgrey}a[p]$表示第$p$组物品

$\color{lightgrey}f[i]$ 表示在$i$重量内可以拿到的最大价值

时间复杂度：$O(\max(p)\times \sum_{i = 1}^{n} \max(a[i])\times v)$

空间复杂度：$O(\max(p)\times \sum_{i = 1}^{n} \max(a[i]))$

二维费用背包

性质：顾名思义，选择一个物品将会$\color{red}同时付出两种代价$，每种代价都有承受上限。

模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N, V, M;
    cin>>N>>V>>M;
    vector<vector<int>> dp(V+1,vector<int>(M+1, 0));
    vector<int> v(N+1), m(N+1),w(N+1);
    for (int i=1;i<=N;i++){
        cin>>v[i]>>m[i]>>w[i];
    }
    for(int i=1;i<=N;i++){
        for(int j=V;j>=v[i];j--){
            for(int k=M;k>=m[i];k--){
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]);
            }
        }
    }
    cout<<dp[V][M]<<endl;
    return 0;
}

代码解释：

$\color{skyblue}v$表示背包的容积（最多可以装的代价之和）

$\color{skyblue}n$表示物品件数

$\color{skyblue}v[i]$表示第$i$件物品的重量（代价）

$\color{skyblue}m[i]$表示第$i$件物品的重量（代价）

$\color{skyblue}w[i]$表示第$i$件物品的价值

$\color{skyblue}dp[i][j]$ 表示在$i,j$重量内可以拿到的最大价值

时间复杂度：$O(m \times n \times p)$

空间复杂度：$O(m \times n)$

练习题

01背包

完全背包

多重背包

混合背包

分组背包

二维费用背包

例题：

01背包

精卫填海

重点：dp下标为v

最大约数和

重点：核心代码：

1
2
3
4
5
6
7
N=V;
for(int i=1;i<=N;++i){
	v[i]=i;
	for(int j=1;j<=v[i]/2;j++){
		if(v[i]%j==0) w[i]+=j;
	}
}

5 倍经验日

重点：

1
for(int j=v[i]-1;j>=0;j--)

j>=0

完全背包

A+B Problem（再升级）

十年OI一场空，不开long long见祖宗

多重背包

混合背包

分组背包

二维费用背包

$\color{white}小陈老你干嘛$

给个赞吧，球球了（弱
#总结
背包总结
https://lzj-blog.top/2023/07/06/背包总结/
作者
starfallen
发布于
2023年7月6日
许可协议