Several different university societies have all requested to book the sports hall, request \(k\) having start time \(u_k\in\mathbb{Z}\) and end time \(v_k\in\mathbb{Z}\) and value \(w_k\in\mathbb{N}\). The hall can only fit one activity at a time, and you have to decide which activities to approve. Your task is to implement a dynamic programming algorithm to find a set of non-overlapping activities that achieves the maximum possible total value. In this example below, an optimal allocation is \([B,E,G,H]\) with total value 30.
It is up to you to write down an appropriate Bellman recursion, perhaps along the lines suggested in Lecture 7 slide 4. It’s a good idea to work through your equation and your code on some simple test cases, to convince yourself you have a correct solution. You will have to use a speedup strategy (memoization or bottom-up iteration) to cope with the test cases used by the Moodle tester.
In lecture 7 we looked at the scenario where the values are all equal to 1, and we demonstrated a greedy algorithm and proved it optimal. In the general case, where the values might not all be equal, I am not aware of any greedy solution, so you should use dynamic programming. A dynamic programming solution along the lines suggested in lecture 7 has \(\Theta(n^3)\) running time, where \(n\) is the number of requests. Can you find an algorithm that is \(O(n^2)\)?
Please submit a source file resalloc.py on Moodle. It should implement a function
max_weight_alloc(requests)
# Input: a list of requests of the form (label,start,end,weight),
# where all labels are distinct
# Output: a list of labels of the requests that you approveIf you want to see what input is being fed into your code, just stick in print(requests) and you’ll see it in the output log on Moodle when your code is evaluated.
The tester will run tests with up to 500 requests. If your code takes more than a minute to run, the tester will time out, and it won’t show you the output of your run. To be extra confusing, Moodle will show you the result of the last successful run. To force it to show you your output, you could make it terminate early, e.g. assert len(requests) < 20. Or, better, run your own tests on 500+ items and make sure your code is fast enough! Here’s the request generator used by the tester: requestgen.py