思路分析：

本题并未按照分组背包的想法做，因为个人感觉按照分组背包是在强行往上套

一：状态表示：

dp[i][j] : 表示前i个公司分配j个物品的最大价值

二：状态计算：

dp[i][j] = dp[i-1][j] //不选
         = dp[i-1][j-k] + w[i][k] //选k个

三：本题因为要求方案，所以就不可以优化成一维了

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 16;

int w[N][N];
int dp[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 i = 1;i <= n;++i)
        for(int j = 0;j <= m;++j){
            dp[i][j] = dp[i-1][j];//第i个公司不选
            for(int k = 1;k <= j;++k)
                dp[i][j] = max(dp[i][j], dp[i-1][j-k] + w[i][k]);//选k个
        }

    cout << dp[n][m] << endl;

    vector<vector<int>> ans;

    int i = n, j = m, k = dp[n][m];
    while(i){
        if(k == dp[i-1][j]){
            ans.push_back({i, 0});
            --i;
        }
        else{
            for(int t = 1;t <= j;++t)
                if(dp[i-1][j-t] + w[i][t] == k){
                    ans.push_back({i, t});
                    k -= w[i][t];
                    --i;
                    j -= t;
                    break;
                }
        }
    }

    for(auto t : ans){
        for(auto p : t)
            cout << p << " ";
        cout << endl;
    }

    return 0;
}