动态规划

$O(n^3)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 20;

int f[N][N];    // f[i, j]表示给前i个公司分配了设备，剩余j台设备未分配的最大利润
int g[N][N];    // g[i, j]表示第i个公司分配j台设备的利润

int n, m;

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    //看做分组的多重背包，每组最多分配m个设备        
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k <= j; k++){    //枚举每组的分配设备数
                f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k]);
                }
            }
        }

    printf("%d\n", f[n][m]);
    int tot = m;
    for(int i = n; i >= 1; i--){
        for(int k = 0; k <= m; k++){
            if(f[i][tot] == f[i - 1][tot - k] + g[i][k]){
                tot -= k;
                printf("%d %d\n", i, k);
                break;
                }
            }
        }
    return 0;
}