3

I received a dynamic programming assignment and I need help figuring out the recurrence relation. The problem is similar to the weighted interval problem, but it has a few additional restrictions:

  • You are given a series of N time slots, each of the same duration.
  • Each time slot k, 0 <= k < N, is given a positive weight W[k].
  • For any time interval [i, j] with i < j, the weight W[i,j] of that interval is:
    W[i,j] = W[i+1] + W[i+2] + ... + W[j]
    Notice that the weight W[i] of the first time slot is not counted, hence any interval of length 1 has a weight of 0.

You are given a value T < N and asked to select exactly T time slots such that the sum of the selected time intervals is maximized.

Example: For N = 5, T = 4 and the weights W = (3, 9, 1, 1, 7), selecting W[0, 1] = 9 and W[3, 4] = 7 will give a maximum weight of 16.

Improve this question

1 Answer 1

Reset to default
5

This is a nice little problem... Define S(i, t) to be the max weight possible if the last slot (end of last range) selected was i and among the slots 0..i there are exactly t slots selected.

The DP decision is that we either add w[i] into S(i, t), or we do not because either slot i-1 was selected, or it was not. So we have:

S(i, t) = max ( S(i-1, t-1) + w[i], S(j, t-1) for j = t-2..i-2 )

Cases where t-1>i are meaningless. So the base case is S(i, 1) = 0 for 0 <= i < N, and successive columns (t = 2,...,T) of the DP table are each one shorter than the last. The desired answer is max ( S(j, T) for j = T-1..N-1 )

Happily you can arrange the computation so that the maxima are computed incrementally, run time is O(NT), and space is O(N)

Working out your example, the DP table looks like this:

               t = 
         1    2    3    4
       ------------------
i = 0 |  0
    1 |  0    9   
    2 |  0    1   10
    3 |  0    1    9   11
    4 |  0    7    9   16

The answer is max(11, 16) = 16

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.