机器分配 https://www.acwing.com/problem/content/1015/

总共m台设备，分给n个公司，公司盈利与分配的设备数量有关，不一定是正比

转化成分组背包问题
每个公司当作物品组，每个物品组内的物品为
分配1台 （体积为1 价值为收益）
分配2台 （体积为2 价值为收益）
分配3台 （体积为3 价值为收益）
…
不在这一组选表示分配0台

#include <iostream>
using namespace std;

const int N = 11, M = 16;
int f[N][M], w[N][M], way[N], 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 ++ ) 
            for ( int k = 0; k <= j; k ++ ) 
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
    cout << f[n][m] << endl;

    int j = m;
    for ( int i = n; i >= 1; i -- ) 
        for ( int k = 0; k <= j; k ++ )
            if ( f[i][j] == f[i - 1][j - k] + w[i][k])
            {
                way[i] = k;
                j -= k;
                break;
            }
    for ( int i = 1; i <= n; i ++ ) cout << i << ' ' << way[i] << endl;
    return 0;
}