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");

}