注意：本篇标红字段均是可纳为己用的经验条。
OJ题知识归属：
1、第一题：动态规划 -> 背包问题的分组背包
2、第二题：动态规划 -> 背包问题的分组背包
3、第三题：动态规划 -> 背包问题的混合背包
4、第四题：动态规划 -> 背包问题的多维费用背包
OJ题来源：洛谷
OJ题名：通天之分组背包
OJ题归属：动态规划【分组背包】
解题算法： 动态规划 or 空间优化的动态规划。
#include<iostream> #include<vector> using namespace std; typedef pair<int, int> PII; const int N = 1010; int n, m, cnt; vector<PII> va[N]; int f[N][N]; int main() { cin >> m >> n; for (int i = 1; i <= n; i++) { int a, b, c; cin >> a >> b >> c; va[c].push_back({ a, b }); cnt = max(cnt, c); } for (int i = 1; i <= cnt; i++) { for (int j = m; j >= 0; j--) { f[i][j] = f[i - 1][j]; for (auto& e : va[i]) //遍历一组里面的物品 { int a = e.first, b = e.second; if (j >= a) f[i][j] = max(f[i][j], f[i - 1][j - a] + b); } } } cout << f[cnt][m] << endl; return 0; } //空间优化 #include<iostream> #include<vector> using namespace std; typedef pair<int, int> PII; const int N = 1010; int n, m, cnt; vector<PII> va[N]; int f[N]; int main() { cin >> m >> n; for (int i = 1; i <= n; i++) { int a, b, c; cin >> a >> b >> c; va[c].push_back({ a, b }); cnt = max(cnt, c); } for (int i = 1; i <= cnt; i++) { for (int j = m; j >= 0; j--) { for (auto& e : va[i]) //遍历一组里面的物品 { int a = e.first, b = e.second; if (j >= a) f[j] = max(f[j], f[j - a] + b); } } } cout << f[m] << endl; return 0; }
OJ题来源：洛谷
OJ题名：排兵布阵
OJ题归属：动态规划【分组背包】
解题算法： 动态规划 or 空间优化的动态规划。
这一题本质是普通的分组背包，只是在使用动态规划算法前，需要将题目给的数据整理成适合动态规划算法的数据格式。
题目里：
城堡 -> 一个组；
玩家对城堡投入的兵力转化后 -> 组内数据；
“我”这个玩家投入的兵力 -> 是一个标线 -> 在标线之下的组内数据都是可以拿走的，实现这个，就需要用 sort 对组内数据进行排序，而 sort 只对行起效，对列没用 -> 翻转数据棋盘。
f[i][j]表示：在前 i 个城堡中挑选，在不超过兵力 j 的情况下，可以得到的最大分数。
#include<iostream> #include<algorithm> using namespace std; const int N = 110, M = 2e4 + 10; int s, n, m; int a[N][N]; int f[N][M]; int main() { cin >> s >> n >> m; for (int i = 1; i <= s; i++) { for (int j = 1; j <= n; j++) { cin >> a[j][i]; a[j][i] = a[j][i] * 2 + 1; } } //给每个堡垒的那组数据排序 for (int i = 1; i <= n; i++) { sort(a[i] + 1, a[i] + 1 + s); } //填dp表 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = f[i - 1][j]; for (int k = 1; k <= s && a[i][k] <= j; k++) { f[i][j] = max(f[i][j], f[i - 1][j - a[i][k]] + k * i); } } } cout << f[n][m] << endl; return 0; } //空间优化 #include<iostream> #include<algorithm> using namespace std; const int N = 110, M = 2e4 + 10; int s, n, m; int a[N][N]; int f[M]; int main() { cin >> s >> n >> m; for (int i = 1; i <= s; i++) { for (int j = 1; j <= n; j++) { cin >> a[j][i]; a[j][i] = a[j][i] * 2 + 1; } } //给每个堡垒的那组数据排序 for (int i = 1; i <= n; i++) { sort(a[i] + 1, a[i] + 1 + s); } //填dp表 for (int i = 1; i <= n; i++) { for (int j = m; j >= 0; j--) { for (int k = 1; k <= s && a[i][k] <= j; k++) { f[j] = max(f[j], f[j - a[i][k]] + k * i); } } } cout << f[m] << endl; return 0; }
OJ题来源：洛谷
OJ题名：樱花
OJ题归属：动态规划【混合背包】
解题算法： 分类讨论 + 动态规划。
经验总结：01背包其实包含在多重背包的，是从多重背包 "k = 1" 这个分支单独拿出来的。
#include<iostream> using namespace std; const int N = 1e4 + 10, M = 1e3 + 10; int n, m; int t[N], c[N], p[N]; int f[M]; int main() { int t1, t2, t3, t4; char ch; cin >> t1 >> ch >> t2 >> t3 >> ch >> t4 >> n; m = t3 * 60 + t4 - (t1 * 60 + t2); for (int i = 1; i <= n; i++) cin >> t[i] >> c[i] >> p[i]; for (int i = 1; i <= n; i++) { if (p[i] == 0)//完全背包 { for (int j = t[i]; j <= m; j++) { f[j] = max(f[j], f[j - t[i]] + c[i]); } } else if (p[i] == 1)//01背包 { for (int j = m; j >= t[i]; j--) { f[j] = max(f[j], f[j - t[i]] + c[i]); } } else//多重背包 { for (int j = m; j >= t[i]; j--) { for (int k = 1; k <= p[i] && j >= t[i] * k; k++) { f[j] = max(f[j], f[j - t[i] * k] + c[i] * k); } } } } cout << f[m] << endl; return 0; } //01背包合并于多重背包 #include<iostream> using namespace std; const int N = 1e4 + 10, M = 1e3 + 10; int n, m; int t[N], c[N], p[N]; int f[M]; int main() { int t1, t2, t3, t4; char ch; cin >> t1 >> ch >> t2 >> t3 >> ch >> t4 >> n; m = t3 * 60 + t4 - (t1 * 60 + t2); for (int i = 1; i <= n; i++) cin >> t[i] >> c[i] >> p[i]; for (int i = 1; i <= n; i++) { if (p[i] == 0)//完全背包 { for (int j = t[i]; j <= m; j++) { f[j] = max(f[j], f[j - t[i]] + c[i]); } } else//多重背包 or 01背包 ------ 01背包包含在多重背包里面了 { for (int j = m; j >= t[i]; j--) { for (int k = 1; k <= p[i] && j >= t[i] * k; k++) { f[j] = max(f[j], f[j - t[i] * k] + c[i] * k); } } } } cout << f[m] << endl; return 0; }
OJ题来源：洛谷
OJ题名：L国的战斗之间谍
OJ题归属：动态规划【多维费用背包】
解题算法： 空间优化的动态规划。
经验总结：多维费用背包本质是01背包，适配01背包的所有分析方法，只是限制条件变多了。
//三维的空间会爆炸，所以必须要用空间优化优化掉一维 #include<iostream> using namespace std; const int N = 110, M = 1010; int n, m, x; int a[N], b[N], c[N]; int f[M][M]; int main() { cin >> n >> m >> x; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i]; for (int i = 1; i <= n; i++) for (int j = m; j >= b[i]; j--) for (int k = x; k >= c[i]; k--) f[j][k] = max(f[j][k], f[j - b[i]][k - c[i]] + a[i]); cout << f[m][x] << endl; return 0; }
