文章目录
前言
一、动态规划
二、例题，代码
AcWing 2. 01背包问题
本题解析
AC代码
代码优化
AcWing 3. 完全背包问题
本题解析
TLE代码
优化
AC代码
代码优化
AcWing 4. 多重背包问题
本题解析
AC代码
AcWing 5. 多重背包问题 II
本题解析
AC代码
AcWing 9. 分组背包问题
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：动态规划——背包问题，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、动态规划
动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，个人认为是目前接触的所有算法里最绕的…
这里的题目的解题方法来自于：y总的闫氏dp分析法
二、例题，代码
AcWing 2. 01背包问题
本题链接：AcWing 2. 01背包问题
本博客提供本题截图：
本题解析
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int v[N]; //体积 int w[N]; //价值 int f[N][N]; // f[i][j], j体积下前i个物品的最大价值 int main() { 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 ++ ) { f[i][j] = f[i - 1][j]; //不装这个第i件物品 if (j >= v[i]) //如果可以装第i件物品 f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
代码优化
我们把二维数组转为一维数组
这里先给出AC代码，然后去讲解其中的细节
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N]; int main() { 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 = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
首先去解释我们的数组f，这里的f[j]代表的是，在背包容量为j的前提下的最优解
我们可以观察和第一个AC代码的最大差距就是对于我们的第二个for循环，我们的第二个for循环相当于是逆序的，这里来解释一下为什么是逆序：
对于二维数组的状态 (未优化版本)，我们的状态f[i][j]其实是由i - 1这个状态表达出来的，我们可以理解为：小的数据是需要我们去保护的，不能被破坏的，因为我们在优化的过程中，其实动态规划的思维是没有改变的，即该题的实现方式是没有发生改变的，我们只是用了一种更为高效的方式去优化我们的代码，故我们需要维护小的数据，即从大到小去循环遍历，保护我们的小数据，简单来说的话，就是我们如果正序遍历，我们的小数据会被【破坏】，但是我们的大数据是由小数据得到的，故我们为了防止小数据被【破坏】，我们采用逆序的遍历更新方式。
AcWing 3. 完全背包问题
本题链接：AcWing 3. 完全背包问题
本博客提供本题截图：
本题解析
TLE代码
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int main() { 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 ++ ) for (int k = 0; v[i] * k <= j; k ++ ) f[i][j] = max (f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); cout << f[n][m] << endl; return 0; }
优化
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int main() { 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 ++ ) { f[i][j] = f[i - 1][j]; if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
代码优化
有没有感觉这个代码似曾相识呢？可以回去对比一下01背包问题中的代码，我们可以惊讶的发现，完全背包问题和01背包问题的代码大致都一样，只有核心代码处有细小的差别：
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); 01背包
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); 多重背包
所以我们可以按照01背包类似的优化方法去优化，这里注意，01背包问题中每一个f[i, j]状态都是由f[i - 1, j]得到的，这就是唯一和多重背包问题不同的地方，故我们的多重背包的优化即第二重循环为正序即可
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int v[N], w[N]; int f[N]; int main() { 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 = v[i]; j <= m; j ++ ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
