机器分配

2013年11月21日3,3490

题目描述

描述 Description

总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。

输入格式 Input Format

第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利

输出格式 Output Format

最大盈利

样例输入

5 3

8 1 9

3 5 5

9 1 4

2 6 7

2 2 9

样例输出

22

代码

#include<iostream>  
using namespace std;  
int main()  
{  
    int f[11][16]={0},m,n,a[11][16]={0};  
    int i,j; 
    cin>>m>>n;  
    for(i=1;i<=m;i++)  
        for(j=1;j<=n;j++)  
            cin>>a[i][j];  
    for(i=0;i<=n;i++)  
        f[i][0]=0;  
    for(i=0;i<=m;i++)  
        f[0][i]=0;  
    f[1][1]=a[1][1];  
    for(i=1;i<=n;i++)  
        for(j=1;j<=m;j++)  
        {  
            int max=0;  
            for(int k=j;k>=0;k--)  
            if(f[j-k][i-1]+a[k][i]>max)max=f[j-k][i-1]+a[k][i];  
            f[j][i]=max;  
        }  
    cout<<f[m][n];  
    return 0;  
}

#include<iostream>

using namespace std;

int main()

{

int f[11][16]={0},m,n,a[11][16]={0};

int i,j;

cin>>m>>n;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

cin>>a[i][j];

for(i=0;i<=n;i++)

f[i][0]=0;

for(i=0;i<=m;i++)

f[0][i]=0;

f[1][1]=a[1][1];

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

{

int max=0;

for(int k=j;k>=0;k--)

if(f[j-k][i-1]+a[k][i]>max)max=f[j-k][i-1]+a[k][i];

f[j][i]=max;

}

cout<<f[m][n];

return 0;

}

« 硬币找零「JoyOI1015」公路乘车 »

hzwer.com _ Home | http://hzwer.com

机器分配

题目描述

样例输入

样例输出

代码

分类目录

热门文章

Myfriends

近期评论