1013. 机器分配
题意
总公司拥有M 台 相同 的高效设备，准备分给下属的N个分公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问：如何分配这M台设备才能使国家得到的盈利最大？
求出最大盈利值。
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
思路
分组背包裸题
状态表示f[i][j] 表示分配到前 i个公司 已经分配了j 台机器的利润最大值
状态计算：
设 k 表示给当前公司分配 k台机器
则k∈[1,j]
不给当前公司分配机器：f[i][j]=f[i−1][j]
给当前公司分配 k kk 台机器： f[i][j]=f[i−1][j−k]+w[i][k]
最后取max 即可
注意：需要输出具体方案 所以我们求f[i][j] 时从后往前求 这样的到的方案字典序最小
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' #define int long long using namespace std; inline int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } inline int lowbit(int x) { return x & -x; } typedef long long LL; typedef pair<int, int>PII; const int N = 1010; int n, m; int w[N][N]; int f[N][N]; int res[N]; void solve() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%lld", &w[i][j]); } } //前 i 个公司 分配 j 个机器的 利润最大值 for (int i = n; i >= 1; --i) { for (int j = 1; j <= m; ++j) { f[i][j] = f[i + 1][j]; for (int k = 1; k <= m; ++k) { if (j - k >= 0) f[i][j] = max(f[i][j], f[i + 1][j - k] + w[i][k]); } } } cout << f[1][m] << endl; int ans = m; for (int i = 1; i <= n; ++i) { for (int k = 1; k <= m; ++k) { if (ans >= k && f[i][ans] == f[i + 1][ans - k] + w[i][k]) { res[i] = k; ans -= k; break; } } } for (int i = 1; i <= n; ++i) printf("%lld %lld\n", i, res[i]); } signed main() { //int t; cin >> t; //while(t--) solve(); return 0; }
