🧑💻 文章作者：Iareges
🔗 博客主页：https://blog.csdn.net/raelum
⚠️ 转载请注明出处
目录
前言
本文主要介绍常见的四种背包问题，思维导图如下：
一、01背包
💡 现有
N N N 件物品和一个最多能承重 M M M 的背包，第 i i i 件物品的重量是 w i w_i wi，价值是 v i v_i vi。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。
因为每件物品只有选与不选两种状态，所以该问题又称01背包问题。
设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的含义是：**在背包承重为
j
j
j 的前提下，从前
i
i
i 个物品中选能够得到的最大价值**。不难发现
d
p
[
N
]
[
M
]
dp[N][M]
dp[N][M] 就是本题的答案。
如何计算
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 呢？我们可以将它划分为以下两部分：
- 选第 i i i 个物品：由于第 i i i 个物品一定会被选择，那么相当于从前 i − 1 i-1 i−1 个物品中选且总重量不超过 j − w [ i ] j-w[i] j−w[i]，对应 d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i−1][j−w[i]]+v[i]。
- 不选第 i i i 个物品：意味着从前 i − 1 i-1 i−1 个物品中选且总重量不超过 j j j，对应 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]。
结合以上两点可得递推公式：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
+
v
[
i
]
)
dp[i][j] = \max(dp[i-1][j],\;dp[i-1][j-w[i]]+v[i])
dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])
由于下标不能是负数，所以上述递推公式要求
j
≥
w
[
i
]
j\geq w[i]
j≥w[i]。当
j
<
w
[
i
]
j<w[i]
j<w[i] 时，意味着第
i
i
i 个物品无法装进背包，此时
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
]
[
j
]
=
{
d
p
[
i
−
1
]
[
j
]
,
j
<
w
[
i
]
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
+
v
[
i
]
)
,
j
≥
w
[
i
]
dp[i][j]= \begin{cases} dp[i-1][j],&j<w[i] \\ \max(dp[i-1][j],\;dp[i-1][j-w[i]]+v[i]),&j\geq w[i] \end{cases}
dp[i][j]={dp[i−1][j],max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]),j<w[i]j≥w[i]
d
p
dp
dp 数组应当如何初始化呢？当背包承重为
0
0
0 时，显然装不下任何物品，所以
d
p
[
i
]
[
0
]
=
0
(
1
≤
i
≤
N
)
dp[i][0]=0\;(1\leq i\leq N)
dp[i][0]=0(1≤i≤N)。若一个物品也不选（即从前
0
0
0 个物品中选），此时最大价值也是
0
0
0，所以
d
p
[
0
]
[
j
]
=
0
(
0
≤
j
≤
M
)
dp[0][j]=0\;(0\leq j\leq M)
dp[0][j]=0(0≤j≤M)。由此可知，
d
p
dp
dp 数组应当全0初始化，即声明为全局变量。
题目链接：AcWing 2. 01背包问题
#include<bits/stdc++.h>usingnamespace std;constint N =1010;int w[N], v[N];int dp[N][N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++) cin >> w[i]>> v[i];for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){if(j < w[i]) dp[i][j]= dp[i -1][j];else dp[i][j]=max(dp[i -1][j], dp[i -1][j - w[i]]+ v[i]);}}
cout << dp[n][m]<<"\n";return0;}
时间复杂度为
O
(
n
m
)
O(nm)
O(nm)。
1.1 使用滚动数组优化
之前我们用到的
d
p
dp
dp 数组是二维数组，它可以进一步优化成一维数组。
观察递推公式不难发现，
d
p
dp
dp 数组中第
i
i
i 行的元素仅由第
i
−
1
i-1
i−1 行的元素得来，即第
0
0
0 行元素的更新值放到第
1
1
1 行，第
1
1
1 行元素的更新值放到第
2
2
2 行，以此类推。与其把一行的更新值放到新的一行，不如直接就地更新，因此我们的
d
p
dp
dp 数组只需要一行来存储，即一维数组。
去掉
d
p
dp
dp 数组的第一维后，递推公式变成：
d
p
[
j
]
=
{
d
p
[
j
]
,
j
<
w
[
i
]
max
(
d
p
[
j
]
,
d
p
[
j
−
w
[
i
]
]
+
v
[
i
]
)
,
j
≥
w
[
i
]
dp[j]= \begin{cases} dp[j],&j<w[i] \\ \max(dp[j],\;dp[j-w[i]]+v[i]),&j\geq w[i] \end{cases}
dp[j]={dp[j],max(dp[j],dp[j−w[i]]+v[i]),j<w[i]j≥w[i]
即
d
p
[
j
]
=
max
(
d
p
[
j
]
,
d
p
[
j
−
w
[
i
]
]
+
v
[
i
]
)
,
j
≥
w
[
i
]
dp[j]= \max(dp[j],\;dp[j-w[i]]+v[i]),\quad j\geq w[i]
dp[j]=max(dp[j],dp[j−w[i]]+v[i]),j≥w[i]
原先
j
j
j 是从
1
1
1 遍历至
m
m
m 的，现在只需从
w
[
i
]
w[i]
w[i] 遍历至
m
m
m。但，这个遍历顺序真的对吗？
请看下图：
红色箭头表示，在二维数组中，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 由
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
dp[i-1][j-w[i]]
dp[i−1][j−w[i]] 和
d
p
[
i
−
1
]
[
j
]
dp[i-1][j]
dp[i−1][j] 得来，
d
p
[
i
]
[
j
+
w
[
i
]
]
dp[i][j+w[i]]
dp[i][j+w[i]] 由
d
p
[
i
−
1
]
[
j
]
dp[i-1][j]
dp[i−1][j] 和
d
p
[
i
−
1
]
[
j
+
w
[
i
]
]
dp[i-1][j+w[i]]
dp[i−1][j+w[i]] 得来。用一维数组的话来讲就是，第
i
i
i 行的
d
p
[
j
]
dp[j]
dp[j] 由第
i
−
1
i-1
i−1 行的
d
p
[
j
−
w
[
i
]
]
dp[j-w[i]]
dp[j−w[i]] 和
d
p
[
j
]
dp[j]
dp[j] 得来，第
i
i
i 行的
d
p
[
j
+
w
[
i
]
]
dp[j+w[i]]
dp[j+w[i]] 由第
i
−
1
i-1
i−1 行的
d
p
[
j
]
dp[j]
dp[j] 和
d
p
[
j
+
w
[
i
]
]
dp[j+w[i]]
dp[j+w[i]] 得来。
如果
j
j
j 从小到大遍历，那么会先更新
d
p
[
j
]
dp[j]
dp[j] 再更新
d
p
[
j
+
w
[
i
]
]
dp[j+w[i]]
dp[j+w[i]]，这就导致在更新
d
p
[
j
+
w
[
i
]
]
dp[j+w[i]]
dp[j+w[i]] 时使用的是第
i
i
i 行的
d
p
[
j
]
dp[j]
dp[j] 而非第
i
−
1
i-1
i−1 行的
d
p
[
j
]
dp[j]
dp[j]，即当
j
j
j 从小到大遍历时，二维数组的递推式变成了：
d
p
[
i
]
[
j
]
=
{
d
p
[
i
−
1
]
[
j
]
,
j
<
w
[
i
]
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
w
[
i
]
]
+
v
[
i
]
)
,
j
≥
w
[
i
]
dp[i][j]= \begin{cases} dp[i-1][j],&j<w[i] \\ \max(dp[i-1][j],\;dp[i][j-w[i]]+v[i]),&j\geq w[i] \end{cases}
dp[i][j]={dp[i−1][j],max(dp[i−1][j],dp[i][j−w[i]]+v[i]),j<w[i]j≥w[i]
⚠️ 请牢记该式，后续讲解完全背包时会提到它。
这显然是错误的。事实上，让
j
j
j 从大到小遍历就不会出现这个问题。
#include<bits/stdc++.h>usingnamespace std;constint N =1010;int w[N], v[N];int dp[N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++) cin >> w[i]>> v[i];for(int i =1; i <= n; i++)for(int j = m; j >= w[i]; j--)
dp[j]=max(dp[j], dp[j - w[i]]+ v[i]);
cout << dp[m]<<"\n";return0;}
当然，
w
w
w 数组和
v
v
v 数组也是不必要的，我们可以边输入边处理，因此可以得到01背包问题的最终版代码：
#include<bits/stdc++.h>usingnamespace std;constint N =1010;int dp[N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++){int w, v;
cin >> w >> v;for(int j = m; j >= w; j--)
dp[j]=max(dp[j], dp[j - w]+ v);}
cout << dp[m]<<"\n";return0;}
到此为止，可以总结出，当
d
p
dp
dp 数组是二维数组时，
j
j
j**既可以从小到大遍历也可以从大到小遍历**，但当
d
p
dp
dp 数组是一维数组时，
j
j
j**只能从大到小遍历**。
二、完全背包
💡 现有
N N N 种物品和一个最多能承重 M M M 的背包，每种物品都有无限个，第 i i i 种物品的重量是 w i w_i wi，价值是 v i v_i vi。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。
设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的含义是：在背包承重为
j
j
j 的前提下，从前
i
i
i**种**物品中选能够得到的最大价值。
如何计算
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 呢？我们可以将它划分为以下若干部分：
- 选 0 0 0 个第 i i i 种物品：相当于不选第 i i i 种物品，对应 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]。
- 选 1 1 1 个第 i i i 种物品：对应 d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i−1][j−w[i]]+v[i]。
- 选 2 2 2 个第 i i i 种物品：对应 d p [ i − 1 ] [ j − 2 ⋅ w [ i ] ] + 2 ⋅ v [ i ] dp[i-1][j-2\cdot w[i]]+2\cdot v[i] dp[i−1][j−2⋅w[i]]+2⋅v[i]。
⋯ \cdots ⋯
上述过程并不会无限进行下去，因为背包承重是有限的。设第
i
i
i 种物品最多能选
t
t
t 个，于是可知
t
=
⌊
j
w
[
i
]
⌋
t=\lfloor \frac{j}{w[i]}\rfloor
t=⌊w[i]j⌋，从而得到递推式：
d
p
[
i
]
[
j
]
=
max
0
≤
k
≤
t
d
p
[
i
−
1
]
[
j
−
k
⋅
w
[
i
]
]
+
k
⋅
v
[
i
]
dp[i][j]=\max_{0\leq k\leq t} dp[i-1][j-k\cdot w[i]]+k\cdot v[i]
dp[i][j]=0≤k≤tmaxdp[i−1][j−k⋅w[i]]+k⋅v[i]
题目链接：AcWing 3. 完全背包问题
#include<bits/stdc++.h>usingnamespace std;constint N =1010;int w[N], v[N];int dp[N][N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++) cin >> w[i]>> v[i];for(int i =1; i <= n; i++)for(int j =1; j <= m; j++){int t = j / w[i];for(int k =0; k <= t; k++)
dp[i][j]=max(dp[i][j], dp[i -1][j - k * w[i]]+ k * v[i]);}
cout << dp[n][m]<<"\n";return0;}
若将
t
t
t 的值改为
min
(
1
,
j
/
w
[
i
]
)
\min(1,\,j/w[i])
min(1,j/w[i])，则完全背包将退化为01背包。
上述代码的时间复杂度为
O
(
m
2
∑
i
w
i
−
1
)
≈
O
(
m
2
n
)
O(m^2\sum_iw_i^{-1})\approx O(m^2n)
O(m2∑iwi−1)≈O(m2n)，TLE是必然的。
2.1 使用滚动数组优化
考虑
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]，此时第
i
i
i 种物品最多能选
t
1
=
⌊
j
w
[
i
]
⌋
t_1=\lfloor \frac{j}{w[i]} \rfloor
t1=⌊w[i]j⌋ 个，将递推式展开：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
+
v
[
i
]
,
d
p
[
i
−
1
]
[
j
−
2
⋅
w
[
i
]
]
+
2
⋅
v
[
i
]
,
⋮
d
p
[
i
−
1
]
[
j
−
t
1
⋅
w
[
i
]
]
+
t
1
⋅
v
[
i
]
)
\begin{aligned} dp[i][j] = \max(dp[i-1][j],\; &dp[i-1][j-w[i]]+v[i], \\ &dp[i-1][j-2\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-t_1\cdot w[i]]+t_1\cdot v[i]) \end{aligned}
dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i],dp[i−1][j−2⋅w[i]]+2⋅v[i],⋮dp[i−1][j−t1⋅w[i]]+t1⋅v[i])
下面考虑
d
p
[
i
]
[
j
−
w
[
i
]
]
dp[i][j-w[i]]
dp[i][j−w[i]]，此时第
i
i
i 种物品最多能选
t
2
=
⌊
j
−
w
[
i
]
w
[
i
]
⌋
=
⌊
j
w
[
i
]
−
1
⌋
=
t
1
−
1
t_2=\lfloor \frac{j-w[i]}{w[i]} \rfloor=\lfloor \frac{j}{w[i]}-1\rfloor=t_1-1
t2=⌊w[i]j−w[i]⌋=⌊w[i]j−1⌋=t1−1 个，相应的递推式为
d
p
[
i
]
[
j
−
w
[
i
]
]
=
max
(
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
,
d
p
[
i
−
1
]
[
j
−
w
[
i
]
−
w
[
i
]
]
+
v
[
i
]
,
d
p
[
i
−
1
]
[
j
−
w
[
i
]
−
2
⋅
w
[
i
]
]
+
2
⋅
v
[
i
]
,
⋮
d
p
[
i
−
1
]
[
j
−
w
[
i
]
−
t
2
⋅
w
[
i
]
]
+
t
2
⋅
v
[
i
]
)
\begin{aligned} dp[i][j-w[i]] = \max(dp[i-1][j-w[i]],\; &dp[i-1][j-w[i]-w[i]]+v[i], \\ &dp[i-1][j-w[i]-2\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-w[i]-t_2\cdot w[i]]+t_2\cdot v[i]) \end{aligned}
dp[i][j−w[i]]=max(dp[i−1][j−w[i]],dp[i−1][j−w[i]−w[i]]+v[i],dp[i−1][j−w[i]−2⋅w[i]]+2⋅v[i],⋮dp[i−1][j−w[i]−t2⋅w[i]]+t2⋅v[i])
又注意到
t
1
=
t
2
+
1
t_1=t_2+1
t1=t2+1，上式可化简为
d
p
[
i
]
[
j
−
w
[
i
]
]
=
max
(
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
,
d
p
[
i
−
1
]
[
j
−
2
⋅
w
[
i
]
]
+
v
[
i
]
,
d
p
[
i
−
1
]
[
j
−
3
⋅
w
[
i
]
]
+
2
⋅
v
[
i
]
,
⋮
d
p
[
i
−
1
]
[
j
−
t
1
⋅
w
[
i
]
]
+
(
t
1
−
1
)
⋅
v
[
i
]
)
\begin{aligned} dp[i][j-w[i]] = \max(dp[i-1][j-w[i]],\; &dp[i-1][j-2\cdot w[i]]+v[i], \\ &dp[i-1][j-3\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-t_1\cdot w[i]]+(t_1-1)\cdot v[i]) \end{aligned}
dp[i][j−w[i]]=max(dp[i−1][j−w[i]],dp[i−1][j−2⋅w[i]]+v[i],dp[i−1][j−3⋅w[i]]+2⋅v[i],⋮dp[i−1][j−t1⋅w[i]]+(t1−1)⋅v[i])
将该式与
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的递推式比较不难发现
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
w
[
i
]
]
+
v
[
i
]
)
dp[i][j]=\max(dp[i-1][j],\;dp[i][j-w[i]]+v[i])
dp[i][j]=max(dp[i−1][j],dp[i][j−w[i]]+v[i])
根据1.1节中的结论，该式对应的是
j
j
j 从小到大遍历，于是我们**只需把01背包问题的代码中的
j
j
j 改为从小到大遍历即可**。
#include<bits/stdc++.h>usingnamespace std;constint N =1010;int dp[N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++){int w, v;
cin >> w >> v;for(int j = w; j <= m; j++)// 只需修改这一行
dp[j]=max(dp[j], dp[j - w]+ v);}
cout << dp[m]<<"\n";return0;}
优化后的时间复杂度为
O
(
n
m
)
O(nm)
O(nm)。
三、多重背包
💡 现有
N N N 种物品和一个最多能承重 M M M 的背包，第 i i i 种物品的数量是 s i s_i si，重量是 w i w_i wi，价值是 v i v_i vi。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。
回顾完全背包问题的暴力解法，在背包承重为
j
j
j 的前提下，第
i
i
i 种物品最多能放
t
=
j
/
w
[
i
]
t=j/w[i]
t=j/w[i] 个（这里是整除）。而在01背包问题中，第
i
i
i 种物品只有一个，所以应当取
t
=
min
(
1
,
j
/
w
[
i
]
)
t=\min(1,\,j/w[i])
t=min(1,j/w[i])。由此可见，对于多重背包问题，只需取
t
=
min
(
s
[
i
]
,
j
/
w
[
i
]
)
t=\min(s[i],\,j/w[i])
t=min(s[i],j/w[i])。
对完全背包问题的暴力解法做一点简单修改即可求解多重背包问题。
题目链接：AcWing 4. 多重背包问题
#include<bits/stdc++.h>usingnamespace std;constint N =110;int dp[N][N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++){int w, v, s;
cin >> w >> v >> s;for(int j =1; j <= m; j++){int t =min(s, j / w);// 只有这里需要修改for(int k =0; k <= t; k++)
dp[i][j]=max(dp[i][j], dp[i -1][j - k * w]+ k * v);}}
cout << dp[n][m]<<"\n";return0;}
时间复杂度为
O
(
m
∑
i
s
i
)
O(m\sum_i s_i)
O(m∑isi)，但还可以进一步优化。
3.1 使用二进制优化
从时间复杂度的表达式可以看出，
O
(
m
)
O(m)
O(m) 的部分已经无法再优化了，我们只能从
O
(
∑
i
s
i
)
O(\sum_i s_i)
O(∑isi) 入手。
先来看一个例子。水果店里有
40
40
40 个苹果，小明计划购买
n
(
1
≤
n
≤
40
)
n\,(1\leq n\leq 40)
n(1≤n≤40) 个苹果，试问如何让小明尽可能快速地完成购买？一个显而易见的暴力做法是，让小明一个个拿（**单位是个**），但效率过于低下。事实上，店员可事先准备好
6
6
6 个箱子，每个箱子中的苹果数量分别为
[
1
,
2
,
4
,
8
,
16
,
9
]
[1,2,4,8,16,9]
[1,2,4,8,16,9]，再让小明按箱子拿（**单位是箱子**），无论小明计划购买多少个，他最多只需要拿
6
6
6 次，而在暴力做法中，小明最多需要拿
40
40
40 次。
下面用数学语言来描述上面的例子。对于任意的正整数
s
s
s，我们都可以找到
⌊
log
2
s
⌋
+
1
≜
k
\lfloor \log_2 s\rfloor+1\triangleq k
⌊log2s⌋+1≜k 个正整数
a
1
,
⋯
,
a
k
a_1,\cdots,a_k
a1,⋯,ak，使得
∀
n
∈
[
0
,
s
]
\forall\, n\in[0,s]
∀n∈[0,s]，都有
n
=
v
T
a
,
a
=
(
a
1
,
⋯
,
a
k
)
T
,
a
i
=
{
2
i
−
1
,
1
≤
i
≤
k
−
1
s
−
2
k
−
1
+
1
(
∈
[
1
,
2
k
−
1
]
)
,
i
=
k
n=v^\mathrm{T}a,\quad a=(a_1,\cdots,a_k)^\mathrm{T},\quad a_i= \begin{cases} 2^{i-1},&1\leq i\leq k -1\\ s-2^{k-1}+1\,(\in [1,\,2^{k-1}]),&i=k\\ \end{cases}
n=vTa,a=(a1,⋯,ak)T,ai={2i−1,s−2k−1+1(∈[1,2k−1]),1≤i≤k−1i=k
其中
v
=
(
v
1
,
⋯
,
v
k
)
T
v=(v_1,\cdots,v_k)^\mathrm{T}
v=(v1,⋯,vk)T，且其分量非
0
0
0 即
1
1
1。
感兴趣的读者可自行证明，这里不再赘述。回到本题，先不考虑背包的承重，我们在暴力求解多重背包的时候，对于每种物品
i
i
i，都要从
0
0
0 逐个枚举至
s
[
i
]
s[i]
s[i]，效率无疑是低下的。现在，对于每种物品
i
i
i，我们将这
s
[
i
]
s[i]
s[i] 个物品分散至
⌊
log
2
s
[
i
]
⌋
+
1
\lfloor \log_2 s[i]\rfloor+1
⌊log2s[i]⌋+1 个「箱子」中，于是多重背包便化成了01背包。
题目链接：AcWing 5. 多重背包问题 II
多重背包问题中的一个「箱子」相当于01背包问题中的一件「物品」，因此我们需要估计出多重背包问题中到底有多少个箱子。显然箱子总数为
N
=
∑
i
=
1
n
(
⌊
log
2
s
[
i
]
⌋
+
1
)
≤
∑
i
=
1
n
⌊
log
2
2000
⌋
+
n
=
11
n
≤
11000
N=\sum_{i=1}^n(\lfloor \log_2 s[i]\rfloor+1)\leq \sum_{i=1}^n \lfloor \log_2 2000\rfloor+n=11n\leq 11000
N=i=1∑n(⌊log2s[i]⌋+1)≤i=1∑n⌊log22000⌋+n=11n≤11000
#include<bits/stdc++.h>usingnamespace std;constint N =11010, M =2010;int w[N], v[N];int dp[M];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;int cnt =0;while(n--){int a, b, s;// a是重量, b是价值, c是数量
cin >> a >> b >> s;for(int k =1; k <= s; k *=2){
cnt++;
w[cnt]= a * k, v[cnt]= b * k;
s -= k;}if(s >0){
cnt++;
w[cnt]= a * s, v[cnt]= b * s;}}
n = cnt;for(int i =1; i <= n; i++)for(int j = m; j >= w[i]; j--)
dp[j]=max(dp[j], dp[j - w[i]]+ v[i]);
cout << dp[m]<<"\n";return0;}
优化后的时间复杂度为
O
(
m
∑
i
log
s
i
)
O(m\sum_i \log s_i)
O(m∑ilogsi)。
四、分组背包
💡 现有
N N N 组物品和一个最多能承重 M M M 的背包，每组物品有若干个，同一组内的物品最多只能选一个。每件物品的重量是 w i j w_{ij} wij，价值是 v i j v_{ij} vij，其中 i i i 是组号， j j j 是组内编号。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。
设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的含义是：在背包承重为
j
j
j 的前提下，从前
i
i
i**组**物品中选能够得到的最大价值。
如何计算
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 呢？我们可以将它划分为以下若干部分：
- 不选第 i i i 组的物品：对应 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]。
- 选第 i i i 组的第 1 1 1 个物品：对应 d p [ i − 1 ] [ j − w [ i ] [ 1 ] ] + v [ i ] [ 1 ] dp[i-1][j-w[i][1]]+v[i][1] dp[i−1][j−w[i][1]]+v[i][1]。
- 选第 i i i 组的第 2 2 2 个物品：对应 d p [ i − 1 ] [ j − w [ i ] [ 2 ] ] + v [ i ] [ 2 ] dp[i-1][j-w[i][2]]+v[i][2] dp[i−1][j−w[i][2]]+v[i][2]。
⋯ \cdots ⋯- 选第 i i i 组的第 s [ i ] s[i] s[i] 个物品：对应 d p [ i − 1 ] [ j − w [ i ] [ s [ i ] ] ] + v [ i ] [ s [ i ] ] dp[i-1][j-w[i][s[i]]]+v[i][s[i]] dp[i−1][j−w[i][s[i]]]+v[i][s[i]]。
直接将
d
p
dp
dp 数组优化到一维可得递推式：
d
p
[
j
]
=
max
(
d
p
[
j
]
,
max
1
≤
k
≤
s
[
i
]
d
p
[
j
−
w
[
i
]
[
k
]
]
+
v
[
i
]
[
k
]
)
dp[j]=\max(dp[j],\;\max_{1\leq k\le s[i]} dp[j-w[i][k]]+v[i][k])
dp[j]=max(dp[j],1≤k≤s[i]maxdp[j−w[i][k]]+v[i][k])
题目链接：AcWing 9. 分组背包问题
#include<bits/stdc++.h>usingnamespace std;constint N =110;int w[N][N], v[N][N], s[N];int dp[N];intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);int n, m;
cin >> n >> m;for(int i =1; i <= n; i++){
cin >> s[i];for(int j =1; j <= s[i]; j++)
cin >> w[i][j]>> v[i][j];}for(int i =1; i <= n; i++)for(int j = m; j >=1; j--)for(int k =1; k <= s[i]; k++)if(j >= w[i][k])
dp[j]=max(dp[j], dp[j - w[i][k]]+ v[i][k]);
cout << dp[m]<<"\n";return0;}
总结
我们可以用一个公式来表示01背包、完全背包和多重背包：
d
p
[
i
]
[
j
]
=
max
0
≤
k
≤
t
d
p
[
i
−
1
]
[
j
−
k
⋅
w
[
i
]
]
+
k
⋅
v
[
i
]
,
t
=
{
min
(
1
,
j
/
w
[
i
]
)
,
01
背包
min
(
+
∞
,
j
/
w
[
i
]
)
=
j
/
w
[
i
]
,
完全背包
min
(
s
[
i
]
,
j
/
w
[
i
]
)
,
多重背包
dp[i][j]=\max_{0\leq k\leq t} dp[i-1][j-k\cdot w[i]]+k\cdot v[i],\quad t=\begin{cases} \min(1,\;j/w[i]),&01背包\\ \min(+\infty,\;j/w[i])=j/w[i],&完全背包 \\ \min(s[i],\;j/w[i]),&多重背包 \end{cases}
dp[i][j]=0≤k≤tmaxdp[i−1][j−k⋅w[i]]+k⋅v[i],t=⎩⎨⎧min(1,j/w[i]),min(+∞,j/w[i])=j/w[i],min(s[i],j/w[i]),01背包完全背包多重背包
本文转载自: https://blog.csdn.net/raelum/article/details/128996521
版权归原作者 Iareges 所有， 如有侵权，请联系我们删除。
版权归原作者 Iareges 所有， 如有侵权，请联系我们删除。