这是一篇背包类问题的博客
01 背包
性质：有一堆物品可以随便取，但每件物品只能拿一次，求能拿到的价值最大为多少。
模板：
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表示背包的容积（最多可以装的代价之和）
N表示物品件数
v[i]表示第i件物品的重量（代价）
w[i]表示第i件物品的价值
dp[i]
表示在i重量内可以拿到的最大价值
时间复杂度：O(N × V)
空间复杂度：O(V)
完全背包（或无限背包）
性质：有一堆物品可以随便取，但每件物品可以随便拿，求能拿到的价值最大为多少。
模板：
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表示背包的容积（最多可以装的代价之和）
n表示物品件数
v[i]表示第i件物品的重量（代价）
w[i]表示第i件物品的价值
dp[i]
表示在i重量内可以拿到的最大价值
时间复杂度：O(n × m)
空间复杂度：O(m)
多重背包
性质：有一堆物品可以随便取，但每件物品有拿的次数上限，求能拿到的价值最大为多少。
模板：
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表示背包的容积（最多可以装的代价之和）
n表示物品件数
v[i]表示第i件物品的重量（代价）
w[i]表示第i件物品的价值
dp[i]
表示在i重量内可以拿到的最大价值
这里头使用了二进制优化，优化有效，证明如下：
要证明多重背包问题的二进制优化是有效的，可以通过对比证明其与原问题的解是等价的，且时间复杂度更低。
二进制优化是将多重背包问题转化为0-1背包问题，具体过程如下：
对于每个物品i，将其拆分为若干个不同重量的0-1背包物品，拆分的原则是采用二进制思想，将物品i拆分为重量为2^k
* w[i]的若干个物品（即2的幂次倍）。
例如，如果物品i的重量w[i]为4，那么拆分为重量为4、8、16、32……的物品。
将拆分后的物品视为0-1背包问题中的普通物品，即每个物品只能选择放入一次。
为了证明二进制优化是有效的，需要证明在使用二进制优化后，所求得的最大价值与原问题的最大价值是相等的。
证明过程如下：
首先考虑原问题的最优解，设其最优解为opt1，每个物品的选择情况为x1, x2, ..., xn。其中xi表示第i个物品的选择数量。
然后考虑二进制优化后的问题的最优解，设其最优解为opt2，每个物品的选择情况为y1, y2, ..., yn′。其中yn′表示第n个物品（拆分后）的选择数量。
在拆分后的问题中，由于每个物品只能选择放入一次，因此拆分后的最优解满足以下条件：
y1 × (2k1 × w[1]) + y2 × (2k2 × w[2]) + ... + yn′ × (2kn′ × 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])，
其中vi表示第i个物品的价值。
综上所述，拆分后的问题最优解opt2的价值与原问题的最优解opt1的价值是相等的。
另外，使用二进制优化后，由于物品数量取决于拆分后每个物品的选择数量，而每个物品的选择数量最多只有log(m/w[i])个（其中w[i]表示第i个物品的重量），因此使用二进制优化后的算法时间复杂度更低，可以达到O(n * log (m/w[i]))。
综上所述，多重背包问题的二进制优化是有效的。
时间复杂度：O(n × log (t) × log (m))
空间复杂度：O(m)
混合背包
性质：有一堆物品可以随便取，但每件物品拿的次数有或没有上限，求能拿到的价值最大为多少。
模板：
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{
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表示背包的容积（最多可以装的代价之和）
n表示物品件数
w[i]表示第i件物品的重量（代价）
c[i]表示第i件物品的价值
p[i]表示第i件物品可以去取得次数上限（为零则可取无限次）
f[i] 表示在i重量内可以拿到的最大价值
时间复杂度：O(n × log (t) × log (m))
空间复杂度：O(m)
分组背包
性质：每组物品有若干个，同一组内的物品最多只能选一个。
模板：
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表示背包的容积（最多可以装的代价之和）
n表示物品件数
w[i]表示第i件物品的重量（代价）
c[i]表示第i件物品的价值
a[p]表示第p组物品
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]))$
二维费用背包
性质：顾名思义，选择一个物品将会同时付出两种代价，每种代价都有承受上限。
模板:
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表示背包的容积（最多可以装的代价之和）
n表示物品件数
v[i]表示第i件物品的重量（代价）
m[i]表示第i件物品的重量（代价）
w[i]表示第i件物品的价值
dp[i][j]
表示在i, j重量内可以拿到的最大价值
时间复杂度：O(m × n × p)
空间复杂度：O(m × 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见祖宗
多重背包
混合背包
分组背包
二维费用背包
小陈老你干嘛
给个赞吧，球球了（弱