One more Problem solved..

1.Let fi(x) = i*(1+log x). Describe a dynamic programming algorithm to input 2 integers x and m and determine how to break x into m integers x1, x2,….xm such that f1(x1) + f2(x2) + …… + fm(xm) is the largest among all possible ways of breaking x into m integers. Note that x >= m and xi >=1 for all i<=i<=m.



DP Recurrence: f[m, X] = max { f[m-1][X-k] + m*(1+log(k)) }
1 <= k <= X-m+1

Table for memorizing Solutions: f[m][X] contains largest value of f(m,X)


Algorithm:

Dp(int m, int X)
{
int i, j, k;
float f_max, t1, t2;

for(i=1; i<=m; i++)
f[i][0] = 0; f[0][i] = 0;

for(i=1; i<=X; i++)
f[1][i] = (1+log(i));

for(i=1; i<=m; i++)
for(j=1; j<=X; j++)
f[i][j] = max { f[i-1][j-k] + i*(1+log(k)) }
1 <= k <= X-m+1
}