题目背景
无
题目描述
总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
输入输出格式
输入格式：
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。
接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。
输出格式：
第1行为最大盈利值
第2到第n为第i分公司分x台
输入输出样例
输入样例#1：
3 3 30 40 50 20 30 50 20 25 30
输出样例#1：
70 1 1 2 1 3 1
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int map[20][20],f[20][20],n,m,kk; 6 void solve(int i,int j){ 7 if(!i) return; 8 for(int k=j;k>=0;k--) 9 if(f[i-1][j-k]+map[i][k]==kk){ 10 kk=f[i-1][j-k]; 11 solve(i-1,j-k); 12 printf("%d %d ",i,k); 13 break; 14 } 15 } 16 int main() 17 { 18 scanf("%d%d",&n,&m); 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=m;j++) 21 scanf("%d",&map[i][j]); 22 for(int i=1;i<=m;i++) f[1][i]=map[1][i];// 赋初始值 23 for(int i=2;i<=n;i++) 24 for(int j=1;j<=m;j++) 25 for(int k=0;k<=j;k++) 26 f[i][j]=max(f[i-1][j-k]+map[i][k],f[i][j]); 27 printf("%d ",f[n][m]); 28 kk=f[n][m]; 29 solve(n,m); 30 return 0; 31 } 32 /*令f[i][j]表示前I 个公司，分配j台机器的最大价值 所以 33 f[i][j]应该由 前i-1个公司分配 j-k台机器推出，得状态转移方程式： 34 f[i][j]=max(f[i-1][j-k]+map[i][k],f[i][j]); 35 对于方案的输出 我觉得更像是 倒着回去 搜索------ 36 */