机器分配

机器分配

【题目描述】

某总公司拥有高效生产设备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;
}