You\'re helping to run a high-performance computing system capable of processing several terabytes of data per day. For each of n days, you\'re presented with a quantity of data; on day i, you\'re presented with x_i terabytes. For each terabyte you process, you receive a fixed revenue, but any unprocessed data becomes unavailable at the end of the day (i.e., you can\'t work on it in any future day). You can\'t always process everything each day because you\'re constrained by the capabilities of your computing system, which can only process a fixed number of terabytes in a given day. In fact, it\'s running some 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 s_1 terabytes, on the second day after a reboot, you can process s_2 terabytes, and so on, up to s_n; we assume s_1 greaterthan s_2 greaterthan s_3 greaterthan middot middot middot s_n greaterthan 0. (Of course, on day i you can only process up to x_i terabytes, regardless of how fast your system is.) To get the system back to peak performance, you can choose to reboot it; but on any day you choose to reboot the system, you can\'t process any data at all. The problem. Given the amounts of available data x_1, x_2, ..., x_n for the next n days, and given the profile of your system as expressed by s_1, s_2, ..., s_n (and starting from a freshly rebooted system on day 1), choose the days on which you\'re going to reboot so as to maximize the total amount of data you process. The best solution would be to reboot on day 2 only; this way, you process 8 terabytes on day 1, then 0 on day 2, then 7 on day 3, then 4 on day 4, for a total of 19. Give an example of an instance with the following properties. - There is a \"surplus\" of data in the sense that x_i greaterthan s_1 for every i. - The optimal solution reboots the system at least twice. In addition to the example, you should say what the optimal solution is. You do not need to provide a proof that it is optimal. Give an efficient algorithm that takes values for x_1, x_2, ..., x_n and s_1, s_2, ..., s_n and returns the total number of terabytes processed by an optimal solution.
(a.) For example, there is no point in rebooting on the last day, since that would just throw away capacity with no benefit. Similarly, there is no point in rebooting two days in a row.
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.
(b.) Algorithm :
def test(list, func):
v = [0]*(len(list)+2)
f_ = 0
for j in range(len(func)):
v[j] = max(v[j-2] + min(func[0],list[j]), v[j-1]+min(list[j], func[f_]))
if v[j] == v[j-2] + min(func[0],list[j]):
f_ = 0
#print \"func[f_]:\", func[f_], v[j-2], min(func[0],list[j]), v[j-1] + min(list[j], func[f_])
f_ += 1
print \"max:\", v[len(list)-1], v[:len(list)]
if __name__ == \"__main__\":
test([10,10,10,10,10], [1,1,1,1,1])
test([10,10,10,10,10], [9,4,3,2,1])
test([0,10,10,10,10], [9,4,3,2,1])
test([0,0,10,10,10], [9,4,3,2,1])
test([10,0,10,0,10], [9,4,3,2,1])
test([10,1,7,7], [8,4,2,1])
test([10,0,10,500,10], [500,4,3,2,1])
Homework Sourse
