1013. 机器分配(分组背包原理，输出方案)

 原题链接e

分组背包问题是互斥选择模型，即一个物品组内只能做出一种决策选择，叫做分组背包问题

分组背包问题，如果运用分组背包模型来做的话，如下转换

每个公司看成一个物品组，我们至多可以选择m个，选择0~m个操作是互斥的，只能做一个，

因此对于分给第 i 个 公司 的不同 机器数量 可以分别看作是一个 物品组 内的 物品

状态计算

初始化：全部初始化为0

状态计算：根据最后一个不同点/最后一次选择来进行划分，可以划分为以下子集

当前选择0个                        dp[i][j]=dp[i-1][j]当前选择1个                        dp[i][j]=dp[i-1][j-1]....当前选择j个                          dp[i][j]=dp[i-1][0]

由于要找出方案具体的选择，但是没有字典序的限制条件，所以可以再遍历一次，记录对于每个公司具体分配了哪些

#include 
#include 
using namespace std;
const int N=1005;
int n,m;
int dp[N][N];
int w[N][N];
int way[N];  //每个公司分配了几个

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++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
            }
    cout<