《算法提高课》题解与笔记上线啦!(链接就是这个)
{: style=”color: #FF0000”}
创建时间2024-1-25
$$ #8 1013.机器分配 $$
分组背包模型
原题Link
Code:
# include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m;
int w[N][N], f[N][N], way[N]; // way用于记录第i个公司所分配到的机器
int main(){
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 ++) // 机器 (一台机器就是1个体积)
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]){
way[i] = k;
j -= k;
break; //只会跳出一层循环,去找下一个公司的机器数量
}
}
}
for(int i = 1; i <= n; i ++) cout << i << ' ' << way[i] << endl; // 输出
return 0;
}
思路