AcWing 1013. 机器分配
原题链接
简单
作者:
妙WA草
,
2022-07-04 10:48:44
,
所有人可见
,
阅读 125
题目描述
AcWing 1013. 机器分配
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,f[15][20],v[15][20],p[20],cnt = 1;
void dfs(int x,int w)
{
if(!x)return;//如果dfs到了第0个物品return
for(int i = 0; i <= w; i ++)
{
if(f[x][w] == f[x - 1][w - i] + v[x][i])//因为输入任意合法方案即可,遇到满足的直接dfs下一层,return掉
{
p[cnt ++] = i;
dfs(x - 1,w - i);
return;
}
}
}
int main()
{
cin >> n >> m;
for(int i = n; i > 0; i --)
for(int j = 1; j <= m; j ++)
cin >> v[i][j] ;
/*
集合:枚举到第i个公司,现在用了j台机器,在这个公司用了k个机器所产生的价值的集合
状态:MAX
转移方程:f[i][j] = max(f[i][j],f[i - 1][j - k] + v[i][k]);
*/
for(int i = 1; i <= n; i ++)
{
for(int j = m; j >= 0; j --)
{
for(int k = 0; k <= j; k ++)
{
f[i][j] = max(f[i][j],f[i - 1][j - k] + v[i][k]);
}
}
}
cout << f[n][m] << endl;
/*
求方案数采用dfs,输入的时候公司倒着输入,则加的最后一层是第一个公司
用p数组存路径
*/
dfs(n,m);
for(int i = 1; i <= n; i ++)
{
cout << i << " " << p[i] <<endl;
}
}