vjonnada
asked on
Dynamic Programming
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.
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.
There must be some other information somewhere about what x and s are and what effect rebooting has. It's not clear enough from what you posted. If you have this information and can share it, someone here might be able to explain it. If you don't have it, I think you will have to get it from somewhere other than here.
ASKER
Hi, Here is the complete problem. Can anyone read this and explain me exactly what it is saying, I am not asking you the entire program. Just give me ideas and explain the logic to do this.
Problem Statement:
To run a high performance computing system capable of
processing several terabytes of data per day .For each of n days ,you are
being presented with a quantity of data; on day i ,you’re presented with xi
terabytes .For each terabyte you process ,you receive a fixed revenue, but any
unprocessed data becomes unavailable(i.e expires) at the end of the day and
thus you can not work on it in subsequent days.
You also can not always process everything each day because you are
constrained by the capabilities of your computing system one-of-a kind software that, while very sophisticated ,is not totally reliable, and so the amount of data you can process goes down with each day that passes since the most recent reboot of the system. On the first day after a reboot, you can process s1 terabytes, on the second day after the reboot ,you can process s2 terabytes ,and so on, up to sn; it is assumed that s1>s2>s3>….>sn>0.Note that on day i you can only process up to xi terabytes, even if the corresponding sj is larger(note the applicable subscripts can be different values).To get the system back to peak performance, you can choose to reboot it; but on any day that you choose to reboot the system, you can not process any data.
• the xi values(i.e x1,x2,….xn) represent the amount of data available(in terabytes) for processing on day i.
• the si values(i.e. s1,s2,…..sn) represent the amount of data(in terabytes) that your system can process on the ith day after a reboot.
Program to print:
• The maximum total amount of data that the system could process( in terabytes).
• The day numbers on which a reboot should occur. Note that there may well be more than one such day number and days start numbering at 1(not 0).
Thanks & regards,
Venkat.
Problem Statement:
To run a high performance computing system capable of
processing several terabytes of data per day .For each of n days ,you are
being presented with a quantity of data; on day i ,you’re presented with xi
terabytes .For each terabyte you process ,you receive a fixed revenue, but any
unprocessed data becomes unavailable(i.e expires) at the end of the day and
thus you can not work on it in subsequent days.
You also can not always process everything each day because you are
constrained by the capabilities of your computing system one-of-a kind software that, while very sophisticated ,is not totally reliable, and so the amount of data you can process goes down with each day that passes since the most recent reboot of the system. On the first day after a reboot, you can process s1 terabytes, on the second day after the reboot ,you can process s2 terabytes ,and so on, up to sn; it is assumed that s1>s2>s3>….>sn>0.Note that on day i you can only process up to xi terabytes, even if the corresponding sj is larger(note the applicable subscripts can be different values).To get the system back to peak performance, you can choose to reboot it; but on any day that you choose to reboot the system, you can not process any data.
• the xi values(i.e x1,x2,….xn) represent the amount of data available(in terabytes) for processing on day i.
• the si values(i.e. s1,s2,…..sn) represent the amount of data(in terabytes) that your system can process on the ith day after a reboot.
Program to print:
• The maximum total amount of data that the system could process( in terabytes).
• The day numbers on which a reboot should occur. Note that there may well be more than one such day number and days start numbering at 1(not 0).
Thanks & regards,
Venkat.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>>>> Similarly, there is no point in rebooting two days in a row.
Don't think that is true. Look at the following table:
x 10 1 2 8
s 8 4 2 1
Obviously it is best to reboot at day 2 *and* at day 3 to catch the 8 capacity at day 4.
I don't have a good algorithm either but you could consider to have a loop where you check whether a reboot is good or not. For that check you recursively need to check the next day and maybe some more. If I understand the statement "note the applicable subscripts can be different values" correctly, the number of indices of s is (much) less than that of x. If so, the number of recursive checks is limited by the number of indices of s.
Regards, Alex
Don't think that is true. Look at the following table:
x 10 1 2 8
s 8 4 2 1
Obviously it is best to reboot at day 2 *and* at day 3 to catch the 8 capacity at day 4.
I don't have a good algorithm either but you could consider to have a loop where you check whether a reboot is good or not. For that check you recursively need to check the next day and maybe some more. If I understand the statement "note the applicable subscripts can be different values" correctly, the number of indices of s is (much) less than that of x. If so, the number of recursive checks is limited by the number of indices of s.
Regards, Alex
> Obviously it is best to reboot at day 2 *and* at day 3 to catch the 8 capacity at day 4.
Somehow this is not obvious to me. If you reboot on days 2 and 3, your output is 8 + 0 + 0 + 8 = 16. If you reboot on day 3 only, your output is 8 + 1 + 0 + 8 = 17.
Somehow this is not obvious to me. If you reboot on days 2 and 3, your output is 8 + 0 + 0 + 8 = 16. If you reboot on day 3 only, your output is 8 + 1 + 0 + 8 = 17.
>>>> your output is 8 + 1 + 0 + 8 = 17.
You are right. That means two reboots on a row never is an option.
That reduces the number of possible solutions to 2^(n-1) - (n-1) what - unfortunately - means that checking all possibilities isn't an efficient method for large n.
Regards, Alex
You are right. That means two reboots on a row never is an option.
That reduces the number of possible solutions to 2^(n-1) - (n-1) what - unfortunately - means that checking all possibilities isn't an efficient method for large n.
Regards, Alex
No comment has been added to this question in more than 21 days, so it is now classified as abandoned.
I will leave the following recommendation for this question in the Cleanup Zone:
Accept: efn {http:#18026244}
Any objections should be posted here in the next 4 days. After that time, the question will be closed.
Sean Durkin
Experts Exchange Cleanup Volunteer
I will leave the following recommendation for this question in the Cleanup Zone:
Accept: efn {http:#18026244}
Any objections should be posted here in the next 4 days. After that time, the question will be closed.
Sean Durkin
Experts Exchange Cleanup Volunteer
Forced accept.
Computer101
EE Admin
Computer101
EE Admin