题目:
总公司拥有高效设备M台, 准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M <= 15,N <= 10。分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。
(非常简洁的题面,没有之一)
输入:
第1行有两个数,第一个数是分公司数N,第二个数是设备台数M。接下来是一个N*M的矩阵,表明了第i个公司分配j台机器的盈利。
输出:
第1行输出最大盈利值。接下来N行,每行2个数,即分公司编号和该分公司获得设备台数。
样例:
3 3 70
30 40 50 ===> 1 1
20 30 50 2 1
20 25 30 3 1
题面也很好理解:找出最大的分配方式,并输出路径。
思路:
1.求最大值,思路是线性dp,第 i 行 j 列的结果只与这一行选几个,和他上面的行选几个有关,所以可以用dp的思路来解。转移方程是
dp[ i ][ j ]=max(dp [ i ][ j ],dp[ i - 1 ][ k ]+a[ i ][ j - k ] );
2.保存路径
这一步是比较难的,对代码能力的要求较高,也是这道题的考点,先上一个比较暴力的,但肯定对的:
void Print(int i,int j){
if(i==0)return;
for(int k=0;k<=j;k++){
if(Max==dp[i-1][k]+a[i][j-k]){
Max=dp[i-1][k];
Print(i-1,k);
printf("%d %d\n",i,j-k);
break;
}
}
}
递归输出,在主函数里Print(n,m)。这样写相当于每一行都重新算了一遍。
(ps:这道题题目要求本来是输出N行,每行包括第 i 家公司和他所选的台数,但是这样递归输出,如果有的公司一台没选,这样的公司是不会输出的)
错误样例:2 2 666
1 666======》 1 2
1 1
(但是这道题的数据太菜了,这样写也能a。。。)
第二种方法:一般的用res数组保存每排每列所选的k,然后输出(我改这个改了11次也没过,哭辽!)
(不要抄这个!不要抄这个!不要抄这个!这个会WA!!!)
就讲一下思路吧。。。
if(dp[i][j]<=dp[i-1][k]+a[i][j-k]){
dp[i][j]=dp[i-1][k]+a[i][j-k];
M[i][j]=k;
}
if(Max<=dp[i][j]){
Max=dp[i][j];
F1=i;F2=j;
}
M[ i ][ j ]保存dp[ i ][ j ]的决策中选的那个k,F i,F j保存最大结果的 i, j 。
因为要从1~N输出,所以需要递归保存一下:
void Print(int i,int j){
if(M[i][j]==0){
ans[i]=j-M[i][j];
return;
}
Print(i-1,M[i][j]);
ans[i]=j-M[i][j];
}
ans[ i ]保存第 i 个公司所选机器数量。
然后输出结果即可。
这道题为什么这样写会WA呢?
附上错误样例:
2 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
大家自己思考一下,这样该怎么输出路径?
显然 1 1 1 0
2 1 2 15
的结果都是一样的,MAX=2。
标准答案和这个代码的结果各据其一。
就是一个多解没spj压正解的题。。。
总结:这道题主要难点有两个,一是转移方程,二是输出路径。
然后就没了。。。