注意本篇标红字段均是可纳为己用的经验条。OJ题知识归属1、第一题动态规划 - 背包问题的分组背包2、第二题动态规划 - 背包问题的分组背包3、第三题动态规划 - 背包问题的混合背包4、第四题动态规划 - 背包问题的多维费用背包OJ题来源洛谷OJ题名通天之分组背包OJ题归属动态规划【分组背包】解题算法 动态规划 or 空间优化的动态规划。#includeiostream #includevector using namespace std; typedef pairint, int PII; const int N 1010; int n, m, cnt; vectorPII 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; } //空间优化 #includeiostream #includevector using namespace std; typedef pairint, int PII; const int N 1010; int n, m, cnt; vectorPII 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 的情况下可以得到的最大分数。#includeiostream #includealgorithm 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; } //空间优化 #includeiostream #includealgorithm 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 这个分支单独拿出来的。#includeiostream 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背包合并于多重背包 #includeiostream 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背包的所有分析方法只是限制条件变多了。//三维的空间会爆炸所以必须要用空间优化优化掉一维 #includeiostream 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; }
