机器分配
题目要求
题目描述：
总公司拥有 M 台相同的高效设备，准备分给下属的 N 个分公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问：如何分配这 M 台设备才能使国家得到的盈利最大？
求出最大盈利值。
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 M 。
输入格式：
第一行有两个数，第一个数是分公司数 N，第二个数是设备台数 M ；
接下来是一个 N ∗ M 的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j台机器时的盈利。
输出格式：
第一行输出最大盈利值；
接下 N 行，每行有 2 个数，即分公司编号和该分公司获得设备台数。
答案不唯一，输出任意合法方案即可。
数据范围：
1≤N≤10,
1≤M≤15
输入样例：
3 3 30 40 50 20 30 50 20 25 30
输出样例：
70 1 1 2 1 3 1
思路分析
可以看做分组背包问题：即每个公司分配的设备数是唯一的，并且要求具体的分配方案，即：背包问题求具体方案；这里其实有两种写法，代码一为按照本博客中的题目：背包问题求具体方案 进行倒枚举，但需注意，倒枚举的话输出的应为:f [ 1 ] [ m ],另一种方法就是记录分配过程，这种方法就不需要进行倒枚举。
代码一
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 15, M = 20; int w[N][M]; int f[N][M]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> w[i][j]; for (int i = n; i >= 1; i -- ) for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= j; k ++ ) f[i][j] = max(f[i][j], f[i + 1][j - k] + w[i][k]); cout << f[1][m] << endl; // 注意是 f[1][m] int j = m; for (int i = 1; i <= n; i ++ ) for (int k = 0; k <= j; k ++ ) if (f[i][j] == f[i + 1][j - k] + w[i][k]) { cout << i << ' ' << k << endl; j -= k; break; } return 0; }
代码二
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 15, M = 20; int w[N][M]; int f[N][M]; int ways[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> w[i][j]; for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]); cout << f[n][m] << endl; int j = m; for (int i = n; i >= 1; i -- ) for (int k = 0; k <= j; k ++ ) if (f[i][j] == f[i - 1][j - k] + w[i][k]) { ways[i] = k; j -= k; break; } for (int i = 1; i <= n; i ++ ) cout << i << ' ' << ways[i] << endl; return 0; }
能量石
题目要求
题目描述：
岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N 块能量石准备开吃。
由于他的嘴很小，所以一次只能吃一块能量石。
能量石很硬，吃完需要花不少时间。
吃完第 i 块能量石需要花费的时间为 S i 秒。
杜达靠吃能量石来获取能量。
不同的能量石包含的能量可能不同。
此外，能量石会随着时间流逝逐渐失去能量。
第 i 块能量石最初包含 E i 单位的能量，并且每秒将失去 L i 单位的能量。
当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。
能量石中包含的能量最多降低至 0 。
请问杜达通过吃能量石可以获得的最大能量是多少？
输入格式：
输出格式：
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 x 是组别编号（从 1 开始），y 是可以获得的最大能量值。
数据范围：
输入样例：
3 4 20 10 1 5 30 5 100 30 1 5 80 60 3 10 4 1000 10 3 1000 10 8 1000 2 12 300 50 5 200 0
输出样例：
Case #1: 105 Case #2: 8 Case #3: 500
样例解释：
在样例 ＃1 中，有N=4个宝石。杜达可以选择的一个吃石头顺序是：
他一共获得了 105 单位的能量，这是能获得的最大值，所以答案是 105 。
在样本案例 ＃2 中，有 N=3个宝石。
无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。
所以他应该吃第三块石头，给他提供 8 单位的能量。
在样本案例 ＃3 中，有N=2 个宝石。杜达可以：
所以答案是 500。
思路分析
memset(f, -0x3f, sizeof f); f[0] = 0;
这样就能保证我们的每一个状态都是由初始状态转移而来，接下来进入贪心分析：
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110, M = 10010; struct Stone{ int s, e, l; bool operator < (const Stone &w) const{ return s * w.l < w.s * l; } }stone[N]; int f[M]; int main() { int T; scanf("%d", &T); for (int C = 1; C <= T; C ++ ) { int n; scanf("%d", &n); memset(f, -0x3f, sizeof f); f[0] = 0; int m = 0; for (int i = 1; i <= n; i ++ ) { int s, e, l; scanf("%d%d%d", &s, &e, &l); stone[i] = {s, e, l}; m += s; } sort(stone + 1, stone + 1 + n); for (int i = 1; i <= n; i ++ ) for (int j = m; j; j -- ) { int s = stone[i].s, e = stone[i].e, l = stone[i].l; if (j >= s) f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l)); } int res = 0; for (int i = 1; i <= m; i ++ ) res = max(res, f[i]); printf("Case #%d: %d\n", C, res); } return 0; }
