Using dynamic programming to maximize work done

Question

Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ work on the second day since a reboot, up to $s_n$. On each consecutive the day the amount of work your computer can perform without being rebooted decreases. In other words, $s_1 >s_2>...>s_n>0$. Any day you reboot your system you cannot do any work.

The problem is to find an algorithm using dynamic programming to figure out the maximum amount of work possible given $x_1...x_n$ and $s_1...s_n$. This means we must determine which day(s), if any, we should reboot on.

For example:

n| 1 | 2 | 3 | 4
x| 8 | 3 | 11| 5
s| 9 | 4 | 2 | 1

The most optimal solution here would be to reboot on day 2, so that we can perform 8 work on day 1, 9 work on day 3, and 4 work on day 4 for a total of 21.

This seems somewhat similar to the partition problem but I am having trouble coming up with a recurrence relation I can convert to dynamic programming.

If we say that our final reboot occurs on day $i$, then our maximum work should be the amount of work done from days $i$ to $n$ plus the maximum work we can do on days $1$ to $i-1$.

So if we say $M[x_1...x_m,s_1...s_n]$ represents the maximum amount of work we can do on days $1$ to $m$, I write the following recurrence relationship:

$$M[x_1...x_m,s_1...s_n] = \max_{i=1}^m\{M[x_1...x_{i-1},s_1...s_n]+R[i]\}$$

Where $R[i]$ is simply the max amount of work you can do from days $i$ to $n$ without rebooting, which is simple to calculate.

Does this seem like it is a valid recurrence relation? Also, I am not quite sure what my base cases would be. Perhaps that $M[x,s] = \{x$ if $s \geq x$ else $s\}$? I am not sure if this covers all possibilities though.

Answer 1

This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it.

Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$

For every $i$, there can be a reboot in any previous day $1\leq j < i$. If it was on day $j$, than you processed $\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\}$ terabytes. Furthermore, on day $j$ you cannot process anything. Than you can define the following recurrence relation: $$ OPT(i) = \displaystyle\max_{1\leq j < i} \left\{\displaystyle\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\} + OPT(j-1)\right\} $$

The algorithm can be implemented in a bottom-up fashion, with $O(n^3)$ running time:

let OPT[0...n] be a new array of n+1 elements
OPT[0] = 0, OPT[1] = min(s[1], x[1])
for i = 2 to n
  m = -infinity
  for j = 1 to i-1
    l = 0
    for k = j+1 to i do l = l + min(s[k-j], x[k])
    l = l + OPT[j-1]
    if l > m then m = l
  OPT[i] = m
return OPT[n]   

There is also a $O(n^2)$ solution based on a matrix of subproblems. Define $OPT(i, j)$ as the maximum from day $i$ to $n$ with last reboot done $j$ days before, more exactly on $i-j$ day. For every day $i$ you have to consider these alternatives:

• you have a reboot. So on day $i$ you cannot process anything: $OPT(i,j) = OPT(i+1, 1)$
• go on with processing: $OPT(i,j) = \min\left\{s_j, x_i\right\} + OPT(i+1, j+1)$

Because it's of no use reboot on last day, you have $OPT(n,j) = \min\left\{s_j, x_n\right\}$.

This last approach is taken from Mangat Rai's work, a user that shared a collection of solutions to Kleinberg's book problems, although the first one i reported is also very close to what you can find there. I suggest you to do a web search for it (no official site as far as i know).