回复:请教解数学题。

来源: 2010-09-07 11:30:28 [旧帖] [给我悄悄话] 本文已被阅读:

Maybe smart guys can see the close form solution right away. Here is one way tackling this problem step by step. Let's forget about the ,000 and assume there are $20 in total. Since the minumal investment is $1, we assign $1 to each project. Now we have $16 left. We need to assign $16 to 4 projects, with the possibility of assign $0 to some projects.

Denote this number by f($16,4), where 16 represents money and 4 represents the number of projects. We now can use dynamic programming.

It is easy to see that f($n,1)=0, f($n, 2)=n+1, and f($n, 3)=f($n,2)+f($n-1,2)+...+f($1,2)+f($0,2)=(n+1)+n+...+2+1=(n*n+3n+2)/2.

Thus, f($n,4)=f($n,3)+f($n-1,3)+...+f($0,3)=[(n*n+3n+2)+...+(1*1+3*1+2)+(0*0+3*0+2)]/2.

The answer to your first question is f($16,4)= HALF OF (16*16+...+1*1)+3*(16+...+1)+17*2.

The answer to your second question is f($16, 5), in which there is a dummy project absorbing the rest money. Of course, you need one more step of recursion.

Does anyone have a better solution procedure?