有限资源分配问题

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file ziyuan.in Output file ziyuan.out

【题目描述】

     设工程项目数为m,资源总数为n,给每项工程分配的资源数目不同,获得的利润也不相同,各工程的投资利润表G如下表所示,其中G[i,j]是对工程i 投资j可获得的利润(1<=i<=m, 0<=j<=n).求如何分配资源才能获得最大的利润。


【输入格式】

输入文件第1行有两个正整数m,n(1<=m,n<=100);

第2~m+1行,每行有n个数,表示对第i个项目分别分配1~n个资源时所获得的利润x(0<x<50000),每两个数据之间用一个空格隔开。

【输出格式】

输出文件只有一行,即把n个资源分配给m个项目所能获得的最大利润,结果保留到小数点后两位。

【样例输入】

  3 6

1.2 1.5 1.85 2.4 2.8 3.3

1.8 2.0 2.25 2.4 2.5 2.6

1.3 1.9 2.2 2.45 2.7 3.0

【样例输出】

5.55