The Weighted Interval Scheduling problem is this: Given a set of weighted interv

Question

The Weighted Interval Scheduling problem is this: Given a set of weighted intervals, choose a set of non-overlapping intervals such that the total weight is maximal.

A weighted interval x can be represented by a triple

       x = (s, f, v),

where

      s = start time of x,    f = finish time of x,   v = weight or value of x

For example, consider the test case for Weighted Interval Scheduling problem depicted below:

These weighted intervals can be represented by the triples

      (0,3,3) (1,4,2) (0,5,4) (3,6,1) (4,7,2) (3,9,5) (5,10,2) (8,10,1)

Write a program to compute a solution to the Weighted Interval Scheduling problem.

Your program must read in a set of weighted intervals. Each interval should be entered as 3 integers. The intervals must be given in a textfile and also be entered in increasing order of finish time. In the above case we would have

       0 3 3    1 4 2   0 5 4    3 6 1 ...

The program should print out the value of the total weight of the optimum solution and the indices of the selected intervals. In the above case, the output would be something like (this output is NOT correct)

   Optimum value: 7

   Interval Sequence: 2 5

The program MUST use recursion. An iterative solution will not receive full credit. Use of memoization will receive 20 points extra credit.

Explanation / Answer

I hope this may help u bit

for j = 1 to n
M[j] = empty <-- solution table
M[j] = 0
M-Compute-Opt(j)
{
if (M[j] is empty)
M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
return M[j]
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.