题目描述

blablabla

样例

思路，枚举 i j  k,i为 公司 编号，j的机器数量， k为第i个公司分配 机器数量，
则总共j个机器1-i-1 个公司  分配机器的数量为j-k  ，
得到的状态转移方程 dp[i][j] =max(dp[i][j] ,dp[i-1][j-k]+w[i][k] ,并记录取得这个 最优效果的前驱
res[i][j]=k(代表的是前面i个公司，分配j个设备最优效果中，且第i个公司分配的个数为 k个
然后利用递归求解 i-1 公司，分配j-res[i][j] 的情况，输出结果 

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

/* 
*/
#include<bits/stdc++.h>
using namespace std;
int w[15][20];//i 公司 编号，j 分配机器数量，得到的效益
int dp[15][20]; 
int n,m;//n个公司 m个设备
int res[15][20];//记录 i公司 ，在总共j 台设备 分配的设备数量 
// 输出 选择的过程 
void dfs(int n,int m)
{
    if(n==0)
    return ;
    else
    {
        dfs(n-1,m-res[n][m]);
        printf("%d %d\n",n,res[n][m]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    // 枚举公司i， 枚举机器j，枚举分割位置k
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            // 前面i-1 分配j-k，第i个公司 k
            for(int k=0;k<=j;k++)
            {
                if(dp[i][j]<=dp[i-1][j-k]+w[i][k])
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]); //前面i-1 分配j-k ，第i公司分配k台 
                    res[i][j]=k;//第i公司在总共j 台情况下分配k ，情况最优 
                }
             } 
        }
     } 
     cout<<dp[n][m]<<endl;
     dfs(n,m);
     return 0;
 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla