AcWing 1013. 机器分配

总公司拥有 M 台 相同 的高效设备，准备分给下属的 N 个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 M。

输入格式

第一行有两个数，第一个数是分公司数 N，第二个数是设备台数 M；

接下来是一个 N×M 的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。

输出格式

第一行输出最大盈利值；

接下 N 行，每行有 22 个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输出任意合法方案即可。

数据范围

1≤N≤10,
1≤M≤15

输入样例：

3 3
30 40 50
20 30 50
20 25 30

输出样例：

70
1 1
2 1
3 1

问题分析；

计算最大盈利值的方法和分组背包一致，合法方案的输出由于没有字典序的限制，所以输出可以比较随意，但必须确保dp顺序和查找输出顺序必须相反。

代码实现：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=25;
int dp[N][N];
vector<int>res;
int w[N][N];
int main(){
    int n,m;
    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];
            for(int k=1;k<=j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
    int s=m;
    for(int i=n;i>=1;i--){
        for(int k=0;k<=s;k++){
            if(dp[i][s]==(dp[i-1][s-k]+w[i][k])){
                res.push_back(k);
                s-=k;
                break;
            }  
        }
    }
    for(int i=res.size()-1;i>=0;i--)cout<<res.size()-i<<" "<<res[i]<<endl;
    return 0;
}