题解 P2066 【机器分配】

说明一下:这道题在刚学动规的我还是很难的，难在它的转移方程和输出 先让我们分析一下这道题的思路：按照经典动态规划的老套路，都要定义那么一个F数组，所以这里我用F[i][j]表示前i个公司分配j台机器所能获得的最大利润，那么在枚举公司时，可以发现这个值是等于前i-1个公司分配k台机器和第i个公司分配j-k台机器的和的最大值（k在0到j之间，注意分配的机器总数可以小于M，也可以为0），那么状态转移方程就出来了：用for循环枚举k的值，F[i][j]=max(F[i-1][k]+V[i][j-k])，再如此循环，可得最终F[N][M]的值 此题的另外一个难点！难点！难点！在于输出！ 定义一个show函数来输出，由于max1是全局变量，所以在主函数循环完之后留下了一个F[N][M]的值，再在主函数中定义k，在枚举k的数值过程中发现k满足了第N个公司分配M-k台机器时，那么第N个公司就分配到了M-k台机器，按理说应当最后输出，所以我们先不急，先将这个值压到栈底，再次进行递归调用将max1的值改变为前N-1个公司分配k台机器的盈利最大值，用i于j传参调用，到了公司枚举完了时，再次调用应该是i=0，所以这个时候应该直接return，再从栈中取出元素输出（代码中有详尽的注释） 很难吧，希望这篇题解对你有帮助！ ```cpp #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; void show(int i,int j); int N,M,max1,V[11][16],F[11][16];//F[i][j]表示第i个公司分配j台机器的最大盈利 int main() { cin>>N>>M; for(int i=1;i<=N;i++) for(int w=1;w<=M;w++) cin>>V[i][w]; //转移方程：前i个公司分配j台机器所获的最大盈利 //应该是前i-1个公司分配k台机器和第i个公司分配 //j-k台机器的盈利和的最大值 for(int i=1;i<=N;i++)//前i个公司 { for(int j=1;j<=M;j++)//分配j台机器 { max1=0;//把max1先往小赋值，便于更新 for(int k=0;k<=j;k++) { int w=F[i-1][k]+V[i][j-k]; if(max1<w) { max1=w; } } F[i][j]=max1;//以上是状态转移方程 } } cout<<F[N][M]<<endl; show(N,M); return 0; } //最难的部分到了！ void show(int i,int j)//i表示前i个公司，j表示前i个公司分到了j台机器 { if(i==0) return;//递归终点 for(int k=0;k<=j;k++)//寻找满足条件的k if(max1==F[i-1][k]+V[i][j-k]) { max1=F[i-1][k];//更新max1便于继续递归 show(i-1,k);//自调用 cout<<i<<" "<<j-k<<endl;//先进后出的栈的输出 break; } } ```