P2066 机器分配
题目背景
无
题目描述
总公司拥有高效设备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按照公司的顺序来分配机器，即按照公司的顺序划分阶段，第一个阶段把M台设备分给第一个公司，记录下来获得的各个盈利值，然后把M台设备分给前两个公司，和第一个阶段比较记录下来更优的各个盈利值，一直到第N个阶段把M台机器全部分给了N个公司，就可以得到最优解，下面来讨论两个阶段之间的关系，设数组F[I][J]表示前I个公司分配J台机器的最大盈利，数组F[I-1][K]表示前I-1个公司分配K台机器的最大盈利(1≤I≤N,1≤J≤M,0≤K≤J),用Value[I][J]表示第I个公司分配 J台机器的盈利, 则F[I][J]可以由下面的式子中取最大值获得： F[I-1][0]+Value[I][J] //前I-1公司分配0台机器最大盈利+第I个公司分配J台的机器的盈利 F[I-1][1]+Value[I][J-1] //前I-1公司分配1台机器最大盈利+第I个公司分配J-1台的机器的盈利 F[I-1][2]+Value[I][J-2] //前I-1公司分配2台机器最大盈利+第I个公司分配J-2台的机器的盈利 F[I-1][J-1]+Value[I][1] //前I-1公司J-1分配台机器最大盈利+第I个公司分配1台的机器的盈利 F[I-1][J]+Value[I][0] //前I-1公司分配J台机器最大盈利+第I个公司分配0台的机器的盈利 在这里用机器数用做每个阶段的状态，由于Value[I][J]的值为定值，要使前面每个式子的值最大，就必须使第i-1阶段的各个状态的值最大，阶段i的状态只能由阶段i-1中的状态通过状态转移方程求得，与其他状态没有关系。由此可见，该问题具备了最优子结构和无后效性原则，适宜使用动态程序设计方法求解。状态转移方程为：F[I][J]=MAX{F[I-1][K]+Value[I][J-K]} (1≤I≤N,1≤J≤M,0≤K≤J) 初始值：F[0][0]=0，F[n][m]的值即为所求最大盈利值。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=30;
6 int map[MAXN][MAXN];
7 int f[MAXN][MAXN];// f[i][j]记录第i个公司分j台机器的最大收益
8 int max1;
9 int show(int i,int j) //输出各分公司分配情况
10 {
11 int k;
12 if (i==0) return 0;
13 for (k=0;k<=j;k++)
14 if (max1==f[i-1][k]+map[i][j-k]) //递归求各公司分配的机器数量
15 {
16 max1=f[i-1][k];
17 show(i-1,k);
18 cout<<i<<" "<<j-k<<endl;
19 break;
20 }
21 }
22
23 int main()
24 {
25 int n;//公司数
26 int m;//机器数
27 scanf("%d%d",&n,&m);
28 for(int i=1;i<=n;i++)
29 for(int j=1;j<=m;j++)
30 scanf("%d",&map[i][j]);
31 for(int i=1;i<=n;i++)
32 for(int j=1;j<=m;j++)
33 {
34 for(int k=0;k<=j;k++)
35 f[i][j]=max(f[i-1][k]+map[i][j-k],f[i][j]);
36 }
37 max1=f[n][m];
38 printf("%d\n",f[n][m]);
39 show(n,m);
40 return 0;
41 }