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

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
}

Dynamic Programming.

Hii people,

The main idea behind this blog is to make a list of Dynamic Programming algorithms for problems. I found some of them over the internet, some from my professors...and some well by me ;). Feel free to add your comments, corrections or improvements to these algos.............also if you know more solutions in DP please add to this blog..... ENJOY!!!!!!!!!!!

1)You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels at mile posts m1 <>

you'd like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 - x)^2. Design an efficient dynamic programming algorithm to determine a sequence of hotels at which to stop so as to minimize the total penalty.

Answer:

DP Recurrence:

P₀ = 0

Pi = min{Pk + (200 - |mi - mk|)2}

0<=k

i.e.,

P[0] = 0

P[i] = min (k=0 to i-1) { P[k] + (200 – abs(m_i – m_k))2}

Where, P_i or P[i] is the minimum Penalty to reach i^th destination.

DP Table:

0

1

2

3

…

n

0

Pn

DP Algorithm (for filling the table):

long minimize_penalty() {

int stops[MAX] = {0}, display[MAX] = {0};

P[0] = 0;

for(i = 1; i <= n_posts; i++) {

P[i] = INFINITY;

for(k = 0; k < style="mso-spacerun:yes"> {

t1 = (200 - abs(M[i] - M[k]));

t1 *= t1;

if((P[k] + t1) < style="mso-spacerun:yes"> {

P[i] = P[k] + t1;

stops[i] = k;

}

}

}

for(i = 1; i <= n_posts; i++) {

printf("\t %d ", P[i]);

}

printf("\n\n Penalty: %d\n Stops: ", P[n_posts]);

i = -1;

k = n_posts;

do {

display[++i] = k;

k = stops[k];

}while(k != 0);

for(k = i; k >= 0; k--)

printf(" %d", display[k]);

printf(" \n");

}