机器分配

【题目描述】

某总公司拥有高效生产设备M 台，准备分给下属的N 个分公司。各分公司若获得这些

设备，可以为总公司提供一定的盈利。问：如何分配这M 台设备才能使国家得到的盈利最

大？求出最大盈利值。

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

【输入格式】

第一行为两个整数M，N。接下来是一个N×M 的矩阵，其中矩阵的第i 行的第j 列的

数Aij 表明第i 个公司分配j 台机器的盈利。所有数据之间用一个空格分隔。

【输出格式】

只有一个数据，为总公司分配这M 台设备所获得的最大盈利。

 最大利润是所有公司都分配所有的机器所得到价值。

 其中某公司可以不分机器

 动规方程为：f[i,j]=max(f[i,j],f[i-1,j-k]+Value[i,k])  (0=<k<=j)

                     f[i,j]表示前i个公司分配j台机器所能获得的最大值。

            Value[i,k]表示第i个公司分配k台机器的获利（输入数据）

    

int f[110][110]={0};//f[i][j]表示前i个公司分配j台机械的最大价值 int c[110][110]={0};    //c[i][j]表示第I个公司分配J台机器的盈利int n, m;int max(int a, int b) {return a > b ? a : b; }int main(){  freopen("machinea.in", "r", stdin);  freopen("machinea.out", "w",stdout);  scanf("%d%d",&m,&n);    for (int i=1;i<=n;++i)     //输入数据     for (int j=1;j<=m;++j)       scanf("%d",&c[i][j]);         for (int i=1;i<=n;++i)     //动态规划处理     for (int j=1;j<=m;++j)  //注意，当k=0的时候，即为f[i][j]=max(f[i][j],f[i-1][j]),  //表示此时第i个公司不占用设备的情况       for (int k=0;k<=j;++k)            f[i][j]= max(f[i][j],f[i-1][j-k]+c[i][k]);  /*注意此处与动规方程f[i,j]=max(f[i-1,j],f[i-1,j-k]+cost[i,k])形式不同    是因为f[i][j]中i公司可以使用设备也可以不使用，当它使用设备时，使用    设备的数量也是可变的，因此当k=0的时候表示f[i][j]中i公司没使用设备	此时f[i-1][j]的值一定会赋值给f[i][j]，然而得到这个值还需要与i公司分配	不同设备数量时的其他值f[i-1][j-k]+v[i][k]进行比较，故动态方程为此形式	*/   printf("%d", f[n][m]);  return 0;}