前言
AcWing算法提高课内容，本文讲解 动态规划
本篇包括以下题目：
⭐️ 多重背包问题 I
⭐️ 多重背包问题 II
⭐️ 多重背包问题 III
⭐️ AcWing 1019. 庆功会
写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵
多重背包问题 I
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示最大价值。
数据范围：
输入样例：
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
思路分析
数据范围很小，暴力枚举即可，不需要过多操作，f[i][j]代表的是只从前 i 件物品中选，且总体积不超过 j的价值最大值。
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[N][N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w); } cout << f[n][m] << endl; return 0; }
代码优化
滚动数组
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[2][N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - k * v] + k * w); } cout << f[n & 1][m] << endl; return 0; }
拷贝数组
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[N], g[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; memcpy(g, f, sizeof f); for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[j] = max(f[j], g[j - k * v] + k * w); } cout << f[m] << endl; return 0; }
逆循环优化
逆循环的优化方式和 01 背包的优化是相同的，原理也是一致的，对于体积逆序枚举即可实现，这样的优化方法可真正实现仅用一维数组表示二维变量：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = m; ~j; j -- ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[j] = max(f[j], f[j - k * v] + k * w); } cout << f[m] << endl; return 0; }
多重背包问题 II
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示最大价值。
数据范围：
输入样例：
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
思路分析
#include <iostream> using namespace std; int main() { int i, cnt = 1, temp = 0; for (i = 1; temp <= 2000; i ++ ) { temp += cnt; cnt *= 2; } cout << i << endl; return 0; }
运行结果为：12 ，即我们需要开的数组大小就为：12 × 1000 + 10 = 12010
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2010, M = 12010; int v[M], w[M]; int f[N]; int main() { int n, m; cin >> n >> m; int cnt = 0; for (int i = 1; i <= n; i ++ ) { int v1, w1, s; cin >> v1 >> w1 >> s; int t = 1; while (t <= s) { cnt ++; v[cnt] = t * v1; w[cnt] = t * w1; s -= t; t *= 2; } if (s) { cnt ++; v[cnt] = s * v1; w[cnt] = s * w1; } } n = cnt; 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; }
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2010, M = 12010, K = 1010; int v[M], w[M]; int f[K][N]; int main() { int n, m; cin >> n >> m; int cnt = 0; for (int i = 1; i <= n; i ++ ) { int v1, w1, s; cin >> v1 >> w1 >> s; int t = 1; while (t <= s) { cnt ++; v[cnt] = t * v1; w[cnt] = t * w1; s -= t; t *= 2; } if (s) { cnt ++; v[cnt] = s * v1; w[cnt] = s * w1; } } n = cnt; for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; if (j >= v[i]) f[i][j] = max (f[i - 1][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
代码优化
既然是转换为了 01背包问题，故我们可以使用 01背包问题优化的思维去优化我们的空间（倒着for循环体积）
