多重背包问题 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; }
庆功会
题目要求
题目描述：
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。
期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
输入格式：
第一行二个数 n ，m ，其中 n 代表希望购买的奖品的种数，m 表示拨款金额。
接下来 n 行，每行 3 个数，v 、w 、s ，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。
输出格式：
一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
数据范围：
n≤500,m≤6000,
v≤100,w≤1000,s≤10
输入样例：
5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1
输出样例：
1040
思路分析
裸题，不做解释，本题用最暴力的解法即可 A C ，有兴趣的读者可以对代码进行二进制优化和单调队列的优化，优化后的代码会放到评论区。
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 6010; 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; }
