机器分配
题目要求
题目描述:
总公司拥有 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; }