AcWing 1013. 机器分配
原题链接
中等
组合背包 递推求方案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int f[N][N],w[N][N];
int n,m;
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 j = 0 ; j <= m ; j++)
for(int k = 1 ; k <= m ; k++)
{
f[i][j] = max(f[i][j],f[i-1][j]);
if(j>=k) f[i][j] = max(f[i][j],f[i-1][j-k]+w[i][k]);
}
}
cout << f[n][m] << endl;
int vol = m;
for(int i = n ; i >= 1 ; i--)
{
bool ok = 0;
for(int j = 1 ; j <= m ; j++)
if(vol - j >=0 && f[i][vol] == f[i-1][vol - j] + w[i][j])
{
cout << i << " " << j << endl;
vol -= j;
ok = 1;
break;
}
if(!ok)
{
cout << i << " " << 0 << endl;
}
}
return 0;
}
AC不了……