NO.89十六届蓝桥杯备战|动态规划-分组背包-混合背包-多维费用背包|通天之分组背包|排兵布阵|樱花|L国的战斗间谍(C++)

P1757 通天之分组背包 - 洛谷

因为⼀个组⾥⾯最多只能挑⼀个元素，所以我们就以⼀个组为单位。

1. 状态表⽰：
   dp[i][j]表⽰从前i 组中挑选物品，总重量不超过j 的情况下，最⼤的价值。
   那么dp[n][m]就是最终结果。
2. 状态转移⽅程：
   根据第i组选什么物品，可以分若⼲情况讨论。设选择的物品重量为a，价值为b，此时的最⼤价值就是dp[i - 1][j - a] + b。
   因为要的是最⼤值，所以考虑所有物品之后，取所有情况的最⼤值就是dp[i][j] 。
3. 初始化：
   全是0 即可

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;const int N = 1010;int n, m, cnt;
vector<PII> g[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> m >> n;for (int i = 1; i <= n; i++){int a, b, c; cin >> a >> b >> c;cnt = max(c, cnt);g[c].push_back({a, b});}//动态规划for (int i = 1; i <= cnt; i++){for (int j = m; j >= 0; j--){f[i][j] = f[i-1][j];//在这一组选for (auto& t : g[i]){int a = t.first, b = t.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 <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;const int N = 1010;int n, m, cnt;
vector<PII> g[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> m >> n;for (int i = 1; i <= n; i++){int a, b, c; cin >> a >> b >> c;cnt = max(c, cnt);g[c].push_back({a, b});}//动态规划for (int i = 1; i <= cnt; i++){for (int j = m; j >= 0; j--){//在这一组选for (auto& t : g[i]){int a = t.first, b = t.second;if (j >= a) f[j] = max(f[j], f[j-a] + b);}}}cout << f[m] << endl;return 0;
}

P5322 [BJOI2019] 排兵布阵 - 洛谷

⼀个城堡⼀个城堡分析，对于第n个城堡，考虑派遣的⼈数应该在所有玩家对这个城堡派遣⼈数中考虑。⽐如⽰例⼆的第三个城堡，我们考虑派遣的⼈数就是1和13 （因为要严格⼤于两倍，⼤⼀点就是最好的）。
因此，把每⼀个城堡看成⼀个⼩组，所有玩家在这个城堡派遣的⼈数看成⼀个⼀个物品，要求的就是在派遣⼈数不超过m 的情况下的最⼤得分，符合分组背包。
⼩优化：对每个城堡中玩家的派遣⼈数从⼩到⼤排序，这样在选择第k个⼈数的时候，总得分就是k × i。

1. 状态表⽰：
   dp[i][j]表⽰：分配前i 个城堡，在总⼈数不超过j 的情况下，最⼤的得分。
   那么dp[n][m]就是最终结果。
2. 状态转移⽅程：
   根据第i个城堡分配的⼈数，分情况讨论。假设分配的是排序后的第k个元素，那么分配⼈数为a[i][k] ，此时的最⼤得分为dp[i - 1][j - a[i][k]] + i × k。
   由于要的是最⼤值，状态转移⽅程就是上述所有合法的k ⾥⾯的最⼤值。
3. 初始化：
   全部为0 即可

#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 2e4 + 10;int s, n, m;
int a[N][N];
int f[N][M];int main()
{ios::sync_with_stdio(false);cin.tie(0);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);        }//分组背包for (int i = 1; i <= n; i++){for (int j = 0; 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;
}

P1833 樱花 - 洛谷

分类讨论

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10, M = 1010;int n, m;
int t[N], c[N], p[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);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] && k*t[i] <= j; k++){f[j] = max(f[j], f[j-t[i]*k] + c[i]*k);        }}}}cout << f[m] << endl;return 0;
}

多重背包和01背包合并

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10, M = 1010;int n, m;
int t[N], c[N], p[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);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 //多重背包或者01背包{for (int j = m; j >= t[i]; j--){for (int k = 1; k <= p[i] && k*t[i] <= j; k++){f[j] = max(f[j], f[j-t[i]*k] + c[i]*k);        }}}}cout << f[m] << endl;return 0;
}

P1910 L 国的战斗之间谍 - 洛谷

⽆⾮就是在01背包的基础上多加了⼀维，那我们就把状态表⽰也加上⼀维即可。

1. 状态表⽰：
   dp[i][j][k]表⽰：从前i个⼈中挑选，伪装能⼒之和不超过j，总⼯资不超过x，此时能获取到的最多资料总数。
   那么dp[n][m][x]就是结果
2. 状态转移⽅程：
   根据第i 个⼈选或者不选分两种情况讨论：
   a. 不选：此时的最多资料为dp[i - 1][j][k] ；
   b. 选：那就要去前i-1各种，凑伪装能⼒之和不超过j-b[i]，总⼯资不超过k-c[i]时的最多⼯资，再加上第i个⼈的⼯资。也就是dp[i - 1][j - b[i]][k - c[i]] + a[i]。
   取上述两种情况的最⼤值即可。注意第⼆种情况要特判⼀下

#include <bits/stdc++.h>
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()
{ios::sync_with_stdio(false);cin.tie(0);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;
}