Another soln of the second post

Given:
x
m
f_i (x) = i * ( 1 + logx)

Objective:
maximize summation(i=1 to m) { f_i (x_i) }

Solution:

Let F = summation(i=1 to m) { f_i (x_i) }
We need to maximize F.

Define G(x,m) = max sum of F when total is x and number of parts required is m.

This function may be defined recursively as follows:

Recurrence:
G (i, j) = max over k=1 to i-j+1 { (m-j+1) * (1+log k) + G (i-k, j-1) }

Base case:
G (i, 1) = m * (1 + log i)

i.e. if we need to break 'i' into 'j' parts, then we try taking the first part as any integer from 1 to i and then solve the remaining subproblem. Also, suppose you need to break 16 into 4 parts, then we only try the range of values for the first part from 1 to 13 and not from 1 to 16. Because, if first part is 16, then other parts would be zeroes and log 0 is undefined and we need to then handle these as separate base cases for the recurrence. Instead, we ensure that while making the recursive call itself, we make a valid one by ranging k from 1 to i-j+1. Also, entries G(i, j) where i
In order write a dynamic programming algorithm based on the above recurrence, use a two-dimensional table T with x rows and m columns. The algorithm is as given below:


for (i = 1 to x-m+1)
T[i, 1] = m * (1 + log i)

for(j = 2 to m)
for(i = j to x-m+j)
max = -1
for(k= 1 to i-j+1)
cost = (m-j+1) * (1+log(k)) + T[i-k, j-1]
if( max < cost)
max = cost
sol[i, j] = i-k
endif
endfor
T[i, j] = max
endfor
endfor