Solved

# Dynamic Programming

Posted on 2006-11-27

Hi all,

I was trying to analyze the following problem but couldnt get any idea of how the total amount of terabytes can be calculated. Could you please help me in understanding the problem. And let me know the better way to do the (dynamic) program.

Problem:

Suppose n=4 and the values of x and s are given by the following table.

Day1 Day2 Day3 Day4

x 10 1 7 7

s 8 4 2 1

The best solution would be to reboot on day2 only; this way, you process 8 terabytes

on day1, then 0 on day2, then 7 on day3, then 4 on day4, for a total of 19.

Note that if you didn't reboot at all, you'd process 8+1+2+1 =12; and other rebooting strategies

give you less than 19 as well.

Give an efficient algorithm that takes values for x1,x2,x3..........xn and

s1,s2,s3........sn and returns the total number of terabytes processed by an optimal solution.

Thanks & Regards,

Venkat.