题目描述

总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

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

输入格式
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；

接下来是一个N*M的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。

输出格式
第一行输出最大盈利值；

接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输入任意合法方案即可。

数据范围
$1≤N≤10, 1≤M≤15$

输入样例

3 3
30 40 50
20 30 50
20 25 30

输出样例

70
1 1
2 1
3 1

算法1

(暴力枚举)

(时间复杂度) $O(n^9)$

暴力枚举加剪枝

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ai[20][20];
int maxn=0;
int maxx[20];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&ai[i][j]);
    for(int a=0;a<=m;a++)
        for(int b=0;b<=m-a;b++)
            for(int c=0;c<=m-a-b;c++)
                for(int d=0;d<=m-a-b-c;d++)
                    for(int e=0;e<=m-a-b-c-d;e++)
                        for(int f=0;f<=m-a-b-c-d-e;f++)
                            for(int g=0;g<=m-a-b-c-d-e-f;g++)
                                for(int h=0;h<=m-a-b-c-d-e-f-g;h++)
                                    for(int i=0;i<=m-a-b-c-d-e-f-g-h;i++)
                                    {
                                        int j=m-a-b-c-d-e-f-g-h-i;
                                                if(maxn<ai[1][a]+ai[2][b]+ai[3][c]+ai[4][d]+ai[5][e]+ai[6][f]+ai[7][g]+ai[8][h]+ai[9][i]+ai[10][j])
                                                {    maxn=ai[1][a]+ai[2][b]+ai[3][c]+ai[4][d]+ai[5][e]+ai[6][f]+ai[7][g]+ai[8][h]+ai[9][i]+ai[10][j];
                                            //  cout<<maxn<<endl;
                                                maxx[1]=a;
                                            maxx[2]=b;
                                        maxx[3]=c;
                                    maxx[4]=d;
                                maxx[5]=e;
                            maxx[6]=f;
                        maxx[7]=g;
                    maxx[8]=h;
                maxx[9]=i;
            maxx[10]=j;
        }}
    printf("%d\n",maxn);
    for(int i=1;i<=n;i++)
//  if(maxx[i]!=0)
    printf("%d %d\n",i,maxx[i]);
    return 0;
}