文章目录
概要说明
本文只讲了01背包和完全背包，至于其他背包问题后续补充
01背包
模板例题
题意概要
思路
01背包的模板题
首先对于背包问题，我们只有两种选择：
选或者不选
选或者不选
选或者不选
我们先设DP状态为
f
(
n
,
W
)
，
n
代表选取物品的数量，
W
代表当前背包可容纳的重量
f(n,W)，n代表选取物品的数量，W代表当前背包可容纳的重量
f(n,W)，n代表选取物品的数量，W代表当前背包可容纳的重量
我们可以先从后往前枚举，在当前
f
(
n
,
W
)
f(n,W)
f(n,W)状态下，不选物品，那么
f
(
n
,
W
)
=
f
(
n
−
1
,
W
)
f(n,W)=f(n-1,W)
f(n,W)=f(n−1,W)
(解释：不选当前的物品，那么物品的总数返回前面一个状态，当前可容纳的重量不变)
选当前物品，那么
f
(
n
,
W
)
=
f
(
n
−
1
,
W
−
w
[
i
]
)
+
v
[
i
]
f(n,W)=f(n-1,W-w[i])+v[i]
f(n,W)=f(n−1,W−w[i])+v[i]
(解释：选当前物品，那么物品的总数返回前面一个状态，当前可容纳的重量减去物品重量，并且加上物品的价值)
剩下依次往前枚举，直到出现
f
(
0
,
W
)
=
0
或者
f
(
n
,
0
)
=
0
结束，即没有物品可以选和可容纳重量为
0
f(0,W)=0或者f(n,0)=0结束，即没有物品可以选和可容纳重量为0
f(0,W)=0或者f(n,0)=0结束，即没有物品可以选和可容纳重量为0
以上是记忆化搜索的步骤，我们可以将上述步骤改为递归
同样分为两种状态：选或者不选
- 不选： d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j]
- 选： d p [ i − 1 ] [ j − v [ i ] ] + w [ i ] dp[i-1][j-v[i]]+w[i] dp[i−1][j−v[i]]+w[i]
那么它的状态转移方程就为： d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])
接下来看代码~~
code1
void solve(){
int n,m;
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=1;j<=m;++j){
if(j<v[i]) dp[i][j]=dp[i-1][j];//当前重量比v[i]小，那么只能不选
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}
cout << dp[n][m] << endl;
return ;
}
对于上述例题来说，这个代码是过不去的
why？这个代码会超出内存限制
那么我们就得优化代码
观察式子，我们发现当前状态
d
p
[
i
]
[
j
]
只跟
d
p
[
i
−
1
]
[
j
]
有关
dp[i][j]只跟dp[i-1][j]有关
dp[i][j]只跟dp[i−1][j]有关，因此我们只需要保留一维，将新的状态覆盖在原状态即可
那么新的状态转移方程为：
f
[
l
]
=
m
a
x
(
f
[
l
]
,
f
[
l
−
w
[
i
]
]
+
v
[
i
]
)
,
l
相当于上述的
j
f[l]=max(f[l],f[l-w[i]]+v[i]),l相当于上述的j
f[l]=max(f[l],f[l−w[i]]+v[i]),l相当于上述的j
(解释：新的状态每次都会覆盖原状态，因此每次都跟自己比较大小即可)
AC代码
code2
void solve(){
int n,W;
cin >> n >> W;
for(int i=1;i<=n;++i){
cin >> w[i] >> v[i];
}
for(int i=1;i<=n;++i)
for(int l=W;l>=w[i];--l){
f[l]=max(f[l],f[l-w[i]]+v[i]);
}
cout << f[W] << endl;
return ;
}
注意：
l
必须从后往前遍历
l必须从后往前遍历
l必须从后往前遍历
如果我们从前往后遍历，那么每次新状态覆盖原状态时，新状态又会覆盖新状态
什么意思呢？
其实我们每次覆盖时，当前那一层是不能覆盖当前那一层的状态的，只能后面一层覆盖前面一层的状态
从前往后遍历，会导致当前层覆盖当前层的状态，这其实就是完全背包(后面来讲)
而我们从后往前遍历，后面的容量不可能比原来的容量大，因此也就不会出现上面这种情况
到此，模板题讲完了，接下来我们来看一道01应用题
01背包的应用题
题目来源
思路
01背包的变形题
分别对4个科目进行DP，首先我们很容易想到：
- 左脑和右脑所花的时间尽可能相同
- 单纯考虑左脑所花的时间，那么就是面临两种选择：做这题 or 不做这题
- 所花的时间为总时间减去左脑所用的时间
首先定义总重W，W的值为单科所花的总时间的一半(尽可能让左右脑所花时间相同)
写出状态状态转移方程：
f
[
k
]
=
m
a
x
(
f
[
k
]
,
f
[
k
−
b
[
j
]
]
+
b
[
j
]
)
;
f[k]=max(f[k],f[k-b[j]]+b[j]);
f[k]=max(f[k],f[k−b[j]]+b[j]);,与01背包不同的是，这题的重量和价值是相同的
算出左脑最多花的时间，ans加上总时间减去
f
[
s
u
m
/
2
]
f[sum/2]
f[sum/2]即单科所花的时间(sum为总时间)
code
void solve(){
for(int i=1;i<=4;++i) cin >> a[i];
for(int i=1;i<=4;++i){
int sum=0;
for(int j=1;j<=a[i];++j){
cin >> b[j];
sum+=b[j];
}
for(int j=1;j<=a[i];++j)
for(int k=sum/2;k>=b[j];--k){
f[k]=max(f[k],f[k-b[j]]+b[j]);
}
ans+=sum-f[sum/2];
for(int j=1;j<=sum/2;++j) f[j]=0;
}
cout << ans << endl;
return ;
}
完全背包
模板例题
题意概要
思路
完全背包的状态转移方程和01背包是一模一样的，都为：
f
[
l
]
=
m
a
x
(
f
[
l
]
,
f
[
l
−
w
[
i
]
]
+
v
[
i
]
)
;
f[l]=max(f[l],f[l-w[i]]+v[i]);
f[l]=max(f[l],f[l−w[i]]+v[i]);
区别就在于
l
l
l是从前往后遍历
例如：背包容量为10 有一个物品重量为1 价值为1
从前往后遍历，
f
[
1
]
=
m
a
x
(
f
[
1
]
,
f
[
1
−
w
[
1
]
]
+
v
[
1
]
)
=
1
f
[
2
]
=
m
a
x
(
f
[
2
]
,
f
[
2
−
w
[
1
]
]
+
v
[
1
]
)
=
2
⋅
⋅
⋅
⋅
⋅
⋅
⋅
f[1]=max(f[1],f[1-w[1]]+v[1])=1 f[2]=max(f[2],f[2-w[1]]+v[1])=2·······
f[1]=max(f[1],f[1−w[1]]+v[1])=1f[2]=max(f[2],f[2−w[1]]+v[1])=2⋅⋅⋅⋅⋅⋅⋅
最终
f
[
10
]
=
10
f[10]=10
f[10]=10
相当于每次遍历都是在原来覆盖过的状态进行下一轮的覆盖
接下来看代码
code
void solve(){
int W,n;
cin >> W >> n;
for(int i=1;i<=n;++i){
cin >> w[i] >> v[i];
}
for(int i=1;i<=n;++i)
for(int l=w[i];l<=W;++l){
f[l]=max(f[l],f[l-w[i]]+v[i]);
}
cout << f[W];
return ;
}