Write a program to implement the Weighted Interval Scheduling problem using top-

Question

Write a program to implement the Weighted Interval Scheduling problem using top-down dynamic programming Your program should read from an input file that looks like the following:

(using C language)

N                                             // number of entries

0 start finish value           // each line has int ID and float start, finish, value.

1 start finish value

…

N-1 start finish value

Hint: your program should call itself recursively with two smaller subproblems, one for the case where the latest starting job is part of the solution and one for the case where the latest starting job is not included in the solution.

Your program should output the best overall value and the list of job IDs which were included in the solution.

Run your program using the following input.

15

0          1          4.5      3

1          5.3      6.1      5.5

2          3          7.2      2

3          6          8          10

4          0.5      10       7

5          7          12.5    4.5

6          8.2      13       3

7          9          15.3    7

8          10.5    16       2

9          9          17.5    9

10       13       19       6

11       16       20.5    8

12       17       23       12

13       20.2    24.1    6

14       19       25       10

Explanation / Answer

use optimization method

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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