问题 5572 --[动归基础]机器分配

5572: [动归基础]机器分配

时间限制: 1 Sec  内存限制: 128 MB
提交: 86  解决: 25
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][76kb]

题目描述


机器分配

assigned.pas/c/cpp

【问题描述】

    总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司若获得这些设备,可以为国家提供一定的盈利。

    问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M<=15,N<=10。

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

【输入数据】:assigned.in

第一行两个数,第一个数是分公司数N,第二个数是设备台数M,。接下来是一个N*M的矩阵,表明了第I个公司分配J台机器的盈利。
【输出数据】:assigned.out
输出第一行为一个整数,表示盈利的最大值

以下n行,每行输出两个数据,分别表示公司编号和分配到的机器数量

【输入样例】
7 6
1 2 3 4 5 6
6 5 4 3 2 1
6 4 8 2 50 194
100 200 300 10 24 72
200 300 400 200 100 50
10 20 30 40 50 60
1 1 1 1 1 1
【输出样例】
700
1 0
2 0
3 0
4 3
5 3
6 0
7 0


输入

输出

提示

来源

[提交][状态]