《机器分配》解答

题目描述

某集团共计配置有M台高效生产设备，计划将其分配至N个下属分支机构。若各分支机构获得相应设备，将为集团创造一定收益。

问：应如何安排这M台设备的分配方案，以实现集团整体收益的最大化？并计算该最大收益值。

分配准则：各分支机构可获取任意数量的设备，但所有分支机构所获设备总数不得超过总设备数量M。

其中M的取值范围不超过100，N的取值范围也不超过100。

输入格式

第一行包含两个整数M和N。随后给出一个由N行M列构成的矩阵，该矩阵中第i行第j列的数值Aij表示第i家公司配置j台设备时所能获得的利润。所有输入数据均以空格作为分隔符。

输出格式

针对总公司配置这M台设备所能实现的最高盈利值，仅有一个相关数据可供参考。

样例数据

input

 3 2

    
 1 2 3
    
 2 3 4
    
    
    
    
    AI写代码cpp

output

    4
    

题解

一**、状态划** 分

由于各企业在获取不同数量的设备时所产生的盈利状况存在差异，因此应以企业作为阶段划分的依据。

二、状态表达方法与实现

当使用一维数组f[i]来表示前i个公司所能实现的最大盈利时，无法明确剩余可分配的机器数量。