多重背包问题 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, 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循环体积）
#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; }
多重背包问题 III
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示最大价值。
数据范围：
输入样例：
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
思路分析
本题用到了单调队列（滑动窗口进行优化），对该知识点不了解或不熟悉的同学请先读博客：单调队列，附上一张y总讲课截图辅助理解：
代码
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010, M = 20010; int v[N], w[N], s[N]; int f[N][M]; int q[M]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i]; for (int i = 1; i <= n; i ++ ) { for (int r = 0; r < v[i]; r ++ ) { int hh = 0, tt = -1; for (int j = r; j <= m; j += v[i] ) { while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++; while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) tt --; q[ ++ tt] = j; f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i]; } } } cout << f[n][m] << endl; return 0; }
代码优化
和 多重背包问题 I 一样的优化方式，我们发现在计算f[i][j]的时候只使用了f[i−1][j]，但是不可以使用 01背包的优化方法，因为我们使用的是 滑动窗口，这致使我们只能正向枚举体积。
滚动数组
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 20010; int f[2][N]; int q[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 r = 0; r < v; r ++ ) { int hh = 0, tt = -1; for (int j = r; j <= m; j += v) { while (hh <= tt && j - q[hh] > s * v) hh ++; while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v * w <= f[(i - 1) & 1][j]) tt --; q[ ++ tt] = j; f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v * w; } } } cout << f[n & 1][m] << endl; return 0; }
拷贝数组
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 20010; int f[N], g[N]; int q[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { memcpy(g, f, sizeof f); int v, w, s; cin >> v >> w >> s; for (int r = 0; r < v; r ++ ) { int hh = 0, tt = -1; for (int j = r; j <= m; j += v) { while (hh <= tt && j - q[hh] > v * s) hh ++; while (hh <= tt && g[q[tt]] + (j - q[tt]) / v * w <= g[j]) tt --; q[ ++ tt] = j; f[j] = g[q[hh]] + (j - q[hh]) / v * w; } } } cout << f[m] << endl; return 0; }
