背包总结

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

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;
}

代码解释：

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

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

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

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

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

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

空间复杂度：O(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;
}

代码解释：

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

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

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

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

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

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

空间复杂度：O(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;
}

代码解释：

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

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

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

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

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

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

要证明多重背包问题的二进制优化是有效的，可以通过对比证明其与原问题的解是等价的，且时间复杂度更低\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，每个物品的选择情况为x1,x2,...,xnx_1, x_2, ..., x_n。其中xix_i表示第i个物品的选择数量。

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

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

由于拆分后的物品覆盖了原问题中所有可能的选择情况，即每个选项都能够用拆分后的物品选择数量的和表示，因此有：
x1×v[1]+x2×v[2]+...+xn×v[n]=y1×(2k1×v[1])+y2×(2k2×v[2])+...+yn′×(2kn′×v[n])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])，
其中viv_i表示第ii个物品的价值。

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

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

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

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

空间复杂度：O(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;
}

代码解释：

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

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

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

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

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

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

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

空间复杂度：O(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;
}

代码解释：

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

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

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

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

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

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

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

空间复杂度：O(max⁡(p)×∑i=1nmax⁡(a[i]))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;
}

代码解释：

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

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

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

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

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

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

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

空间复杂度：O(m×n)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://www.lzj-blog.top/2023/07/06/背包总结/
作者
lzj
发布于
2023年7月6日
许可协议