好久以前做的题了,贴个代码,关于输出方案方面,
看各种题解的感觉有点复杂了,此代码输出方案比较方便直观,当然空间上稍多
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20;
int f[N][N];
int g[N][N];
int last[N][N]; // 当前工厂i在一共选了j个机器下,选择的机器数(话说last是不是写成cnt更直观)
int n, m;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> g[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= j; k ++ )
{
if (f[i][j] < f[i - 1][j - k] + g[i][k])
{
f[i][j] = f[i - 1][j - k] + g[i][k];
last[i][j] = k;
}
}
cout << f[n][m] << endl;
for (int i = n; i; i -- )
{
cout << i << ' ' << last[i][m] << endl;
m -= last[i][m];
}
return 0;
}