题目:

总公司拥有高效设备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压正解的题。。。

总结:这道题主要难点有两个,一是转移方程,二是输出路径。

然后就没了。。。

 

05-25 22:21