母婴网站建设方案,企业网站系统有哪些,健身会所网站模板,哪个网站公司做的好#x1f9d1;#x1f4bb; 文章作者#xff1a;Iareges #x1f517; 博客主页#xff1a;https://blog.csdn.net/raelum ⚠️ 转载请注明出处 目录前言一、01背包1.1 使用滚动数组优化二、完全背包2.1 使用滚动数组优化三、多重背包3.1 使用二进制优化四、分组背包总结… 文章作者Iareges 博客主页https://blog.csdn.net/raelum ⚠️ 转载请注明出处 目录前言一、01背包1.1 使用滚动数组优化二、完全背包2.1 使用滚动数组优化三、多重背包3.1 使用二进制优化四、分组背包总结前言
本文主要介绍常见的四种背包问题思维导图如下 一、01背包 现有 NNN 件物品和一个最多能承重 MMM 的背包第 iii 件物品的重量是 wiw_iwi价值是 viv_ivi。在背包能承受的范围内试问将哪些物品装入背包后可使总价值最大求这个最大价值。 因为每件物品只有选与不选两种状态所以该问题又称01背包问题。
设 dp[i][j]dp[i][j]dp[i][j] 的含义是在背包承重为 jjj 的前提下从前 iii 个物品中选能够得到的最大价值。不难发现 dp[N][M]dp[N][M]dp[N][M] 就是本题的答案。
如何计算 dp[i][j]dp[i][j]dp[i][j] 呢我们可以将它划分为以下两部分
选第 iii 个物品由于第 iii 个物品一定会被选择那么相当于从前 i−1i-1i−1 个物品中选且总重量不超过 j−w[i]j-w[i]j−w[i]对应 dp[i−1][j−w[i]]v[i]dp[i-1][j-w[i]]v[i]dp[i−1][j−w[i]]v[i]。不选第 iii 个物品意味着从前 i−1i-1i−1 个物品中选且总重量不超过 jjj对应 dp[i−1][j]dp[i-1][j]dp[i−1][j]。
结合以上两点可得递推公式
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]) 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]。当 jw[i]jw[i]jw[i] 时意味着第 iii 个物品无法装进背包此时 dp[i][j]dp[i−1][j]dp[i][j]dp[i-1][j]dp[i][j]dp[i−1][j]。综合以上可得出
dp[i][j]{dp[i−1][j],jw[i]max(dp[i−1][j],dp[i−1][j−w[i]]v[i]),j≥w[i]dp[i][j] \begin{cases} dp[i-1][j],jw[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]),jw[i]j≥w[i]
dpdpdp 数组应当如何初始化呢当背包承重为 000 时显然装不下任何物品所以 dp[i][0]0(1≤i≤N)dp[i][0]0\;(1\leq i\leq N)dp[i][0]0(1≤i≤N)。若一个物品也不选即从前 000 个物品中选此时最大价值也是 000所以 dp[0][j]0(0≤j≤M)dp[0][j]0\;(0\leq j\leq M)dp[0][j]0(0≤j≤M)。由此可知dpdpdp 数组应当全0初始化即声明为全局变量。 题目链接AcWing 2. 01背包问题 #include bits/stdc.husing namespace std;const int N 1010;int w[N], v[N];
int dp[N][N];int main() {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;return 0;
}时间复杂度为 O(nm)O(nm)O(nm)。
1.1 使用滚动数组优化
之前我们用到的 dpdpdp 数组是二维数组它可以进一步优化成一维数组。
观察递推公式不难发现dpdpdp 数组中第 iii 行的元素仅由第 i−1i-1i−1 行的元素得来即第 000 行元素的更新值放到第 111 行第 111 行元素的更新值放到第 222 行以此类推。与其把一行的更新值放到新的一行不如直接就地更新因此我们的 dpdpdp 数组只需要一行来存储即一维数组。
去掉 dpdpdp 数组的第一维后递推公式变成
dp[j]{dp[j],jw[i]max(dp[j],dp[j−w[i]]v[i]),j≥w[i]dp[j] \begin{cases} dp[j],jw[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]),jw[i]j≥w[i]
即
dp[j]max(dp[j],dp[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]
原先 jjj 是从 111 遍历至 mmm 的现在只需从 w[i]w[i]w[i] 遍历至 mmm。但这个遍历顺序真的对吗
请看下图 红色箭头表示在二维数组中dp[i][j]dp[i][j]dp[i][j] 由 dp[i−1][j−w[i]]dp[i-1][j-w[i]]dp[i−1][j−w[i]] 和 dp[i−1][j]dp[i-1][j]dp[i−1][j] 得来dp[i][jw[i]]dp[i][jw[i]]dp[i][jw[i]] 由 dp[i−1][j]dp[i-1][j]dp[i−1][j] 和 dp[i−1][jw[i]]dp[i-1][jw[i]]dp[i−1][jw[i]] 得来。用一维数组的话来讲就是第 iii 行的 dp[j]dp[j]dp[j] 由第 i−1i-1i−1 行的 dp[j−w[i]]dp[j-w[i]]dp[j−w[i]] 和 dp[j]dp[j]dp[j] 得来第 iii 行的 dp[jw[i]]dp[jw[i]]dp[jw[i]] 由第 i−1i-1i−1 行的 dp[j]dp[j]dp[j] 和 dp[jw[i]]dp[jw[i]]dp[jw[i]] 得来。
如果 jjj 从小到大遍历那么会先更新 dp[j]dp[j]dp[j] 再更新 dp[jw[i]]dp[jw[i]]dp[jw[i]]这就导致在更新 dp[jw[i]]dp[jw[i]]dp[jw[i]] 时使用的是第 iii 行的 dp[j]dp[j]dp[j] 而非第 i−1i-1i−1 行的 dp[j]dp[j]dp[j]即当 jjj 从小到大遍历时二维数组的递推式变成了
dp[i][j]{dp[i−1][j],jw[i]max(dp[i−1][j],dp[i][j−w[i]]v[i]),j≥w[i]dp[i][j] \begin{cases} dp[i-1][j],jw[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]),jw[i]j≥w[i] ⚠️ 请牢记该式后续讲解完全背包时会提到它。 这显然是错误的。事实上让 jjj 从大到小遍历就不会出现这个问题。
#include bits/stdc.husing namespace std;const int N 1010;int w[N], v[N];
int dp[N];int main() {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;return 0;
}当然www 数组和 vvv 数组也是不必要的我们可以边输入边处理因此可以得到01背包问题的最终版代码
#include bits/stdc.husing namespace std;const int N 1010;int dp[N];int main() {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;return 0;
}到此为止可以总结出当 dpdpdp 数组是二维数组时jjj 既可以从小到大遍历也可以从大到小遍历但当 dpdpdp 数组是一维数组时jjj 只能从大到小遍历。
二、完全背包 现有 NNN 种物品和一个最多能承重 MMM 的背包每种物品都有无限个第 iii 种物品的重量是 wiw_iwi价值是 viv_ivi。在背包能承受的范围内试问将哪些物品装入背包后可使总价值最大求这个最大价值。 设 dp[i][j]dp[i][j]dp[i][j] 的含义是在背包承重为 jjj 的前提下从前 iii 种物品中选能够得到的最大价值。
如何计算 dp[i][j]dp[i][j]dp[i][j] 呢我们可以将它划分为以下若干部分
选 000 个第 iii 种物品相当于不选第 iii 种物品对应 dp[i−1][j]dp[i-1][j]dp[i−1][j]。选 111 个第 iii 种物品对应 dp[i−1][j−w[i]]v[i]dp[i-1][j-w[i]]v[i]dp[i−1][j−w[i]]v[i]。选 222 个第 iii 种物品对应 dp[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⋯
上述过程并不会无限进行下去因为背包承重是有限的。设第 iii 种物品最多能选 ttt 个于是可知 t⌊jw[i]⌋t\lfloor \frac{j}{w[i]}\rfloort⌊w[i]j⌋从而得到递推式
dp[i][j]max0≤k≤tdp[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.husing namespace std;const int N 1010;int w[N], v[N];
int dp[N][N];int main() {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;return 0;
}若将 ttt 的值改为 min(1,j/w[i])\min(1,\,j/w[i])min(1,j/w[i])则完全背包将退化为01背包。
上述代码的时间复杂度为 O(m2∑iwi−1)≈O(m2n)O(m^2\sum_iw_i^{-1})\approx O(m^2n)O(m2∑iwi−1)≈O(m2n)TLE是必然的。
2.1 使用滚动数组优化
考虑 dp[i][j]dp[i][j]dp[i][j]此时第 iii 种物品最多能选 t1⌊jw[i]⌋t_1\lfloor \frac{j}{w[i]} \rfloort1⌊w[i]j⌋ 个将递推式展开
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])\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])
下面考虑 dp[i][j−w[i]]dp[i][j-w[i]]dp[i][j−w[i]]此时第 iii 种物品最多能选 t2⌊j−w[i]w[i]⌋⌊jw[i]−1⌋t1−1t_2\lfloor \frac{j-w[i]}{w[i]} \rfloor\lfloor \frac{j}{w[i]}-1\rfloort_1-1t2⌊w[i]j−w[i]⌋⌊w[i]j−1⌋t1−1 个相应的递推式为
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])\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])
又注意到 t1t21t_1t_21t1t21上式可化简为
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])\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])
将该式与 dp[i][j]dp[i][j]dp[i][j] 的递推式比较不难发现
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]) dp[i][j]max(dp[i−1][j],dp[i][j−w[i]]v[i])
根据1.1节中的结论该式对应的是 jjj 从小到大遍历于是我们只需把01背包问题的代码中的 jjj 改为从小到大遍历即可。
#include bits/stdc.husing namespace std;const int N 1010;int dp[N];int main() {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;return 0;
}优化后的时间复杂度为 O(nm)O(nm)O(nm)。
三、多重背包 现有 NNN 种物品和一个最多能承重 MMM 的背包第 iii 种物品的数量是 sis_isi重量是 wiw_iwi价值是 viv_ivi。在背包能承受的范围内试问将哪些物品装入背包后可使总价值最大求这个最大价值。 回顾完全背包问题的暴力解法在背包承重为 jjj 的前提下第 iii 种物品最多能放 tj/w[i]tj/w[i]tj/w[i] 个这里是整除。而在01背包问题中第 iii 种物品只有一个所以应当取 tmin(1,j/w[i])t\min(1,\,j/w[i])tmin(1,j/w[i])。由此可见对于多重背包问题只需取 tmin(s[i],j/w[i])t\min(s[i],\,j/w[i])tmin(s[i],j/w[i])。
对完全背包问题的暴力解法做一点简单修改即可求解多重背包问题。 题目链接AcWing 4. 多重背包问题 #include bits/stdc.husing namespace std;const int N 110;int dp[N][N];int main() {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;return 0;
}时间复杂度为 O(m∑isi)O(m\sum_i s_i)O(m∑isi)但还可以进一步优化。
3.1 使用二进制优化
从时间复杂度的表达式可以看出O(m)O(m)O(m) 的部分已经无法再优化了我们只能从 O(∑isi)O(\sum_i s_i)O(∑isi) 入手。
先来看一个例子。水果店里有 404040 个苹果小明计划购买 n(1≤n≤40)n\,(1\leq n\leq 40)n(1≤n≤40) 个苹果试问如何让小明尽可能快速地完成购买一个显而易见的暴力做法是让小明一个个拿单位是个但效率过于低下。事实上店员可事先准备好 666 个箱子每个箱子中的苹果数量分别为 [1,2,4,8,16,9][1,2,4,8,16,9][1,2,4,8,16,9]再让小明按箱子拿单位是箱子无论小明计划购买多少个他最多只需要拿 666 次而在暴力做法中小明最多需要拿 404040 次。
下面用数学语言来描述上面的例子。对于任意的正整数 sss我们都可以找到 ⌊log2s⌋1≜k\lfloor \log_2 s\rfloor1\triangleq k⌊log2s⌋1≜k 个正整数 a1,⋯,aka_1,\cdots,a_ka1,⋯,ak使得 ∀n∈[0,s]\forall\, n\in[0,s]∀n∈[0,s]都有
nvTa,a(a1,⋯,ak)T,ai{2i−1,1≤i≤k−1r(∈[1,2k−1]),iknv^\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\\ r\,(\in [1,\,2^{k-1}]),ik\\ \end{cases} nvTa,a(a1,⋯,ak)T,ai{2i−1,r(∈[1,2k−1]),1≤i≤k−1ik
其中 v(v1,⋯,vk)Tv(v_1,\cdots,v_k)^\mathrm{T}v(v1,⋯,vk)T且其分量非 000 即 111。
感兴趣的读者可自行证明这里不再赘述。回到本题先不考虑背包的承重我们在暴力求解多重背包的时候对于每种物品 iii都要从 000 逐个枚举至 s[i]s[i]s[i]效率无疑是低下的。现在对于每种物品 iii我们将这 s[i]s[i]s[i] 个物品分散至 ⌊log2s[i]⌋1\lfloor \log_2 s[i]\rfloor1⌊log2s[i]⌋1 个「箱子」中于是多重背包便化成了01背包。 题目链接AcWing 5. 多重背包问题 II 多重背包问题中的一个「箱子」相当于01背包问题中的一件「物品」因此我们需要估计出多重背包问题中到底有多少个箱子。显然箱子总数为
N∑i1n(⌊log2s[i]⌋1)≤∑i1n⌊log22000⌋n11n≤11000N\sum_{i1}^n(\lfloor \log_2 s[i]\rfloor1)\leq \sum_{i1}^n \lfloor \log_2 2000\rfloorn11n\leq 11000 Ni1∑n(⌊log2s[i]⌋1)≤i1∑n⌊log22000⌋n11n≤11000
#include bits/stdc.husing namespace std;const int N 11010, M 2010;int w[N], v[N];
int dp[M];int main() {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;return 0;
}优化后的时间复杂度为 O(m∑ilogsi)O(m\sum_i \log s_i)O(m∑ilogsi)。
四、分组背包 现有 NNN 组物品和一个最多能承重 MMM 的背包每组物品有若干个同一组内的物品最多只能选一个。每件物品的重量是 wijw_{ij}wij价值是 vijv_{ij}vij其中 iii 是组号jjj 是组内编号。在背包能承受的范围内试问将哪些物品装入背包后可使总价值最大求这个最大价值。 设 dp[i][j]dp[i][j]dp[i][j] 的含义是在背包承重为 jjj 的前提下从前 iii 组物品中选能够得到的最大价值。
如何计算 dp[i][j]dp[i][j]dp[i][j] 呢我们可以将它划分为以下若干部分
不选第 iii 组的物品对应 dp[i−1][j]dp[i-1][j]dp[i−1][j]。选第 iii 组的第 111 个物品对应 dp[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]。选第 iii 组的第 222 个物品对应 dp[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⋯选第 iii 组的第 s[i]s[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]]dp[i−1][j−w[i][s[i]]]v[i][s[i]]。
直接将 dpdpdp 数组优化到一维可得递推式
dp[j]max(dp[j],max1≤k≤s[i]dp[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.husing namespace std;const int N 110;int w[N][N], v[N][N], s[N];
int dp[N];int main() {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;return 0;
}总结
我们可以用一个公式来表示01背包、完全背包和多重背包
dp[i][j]max0≤k≤tdp[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背包完全背包多重背包
