Waldo's World. You arrive at Waldo's World Amusement Park with T minutes remaining until the park closes. The park has n rides and your objective is to complete as many rides as possible before the park closes. (For this problem, taking the same ride twice counts as 2 rides.) You are given a table W such that W(i, t) gives you the waiting time for ride i at time t. For convenience, assume that t is expressed as minutes before the park closes. Ride i itself takes r_i minutes and all times are measured in integer minutes.

Describe a dynamic programming algorithm that produces a schedule of rides with the maximum number of rides.

Additional Instructions: When you are asked to provide a dynamic programming algorithm. You must provide the following:

a. Define a function OPT that can be used to solve this dynamic programming problem. To do this, you must describe the input parameters to OPT and the "return value" using English sentences. (Note: you are specifying the input-output relation of the function. You should not describe how to compute the function.)

b. Give a mathematical formula that shows how OPT can be computed recursively. Then, explain all the major parts of the formula using English sentences. Remember to include the base cases.

c. Describe how OPT can be computed bottom up using a dynamic programming table. Be sure to include a description of the dimensions of the table and the order that the entries of the table are to be filled. Draw a diagram. Which entry has the solution to the original problem?

d. Analyze and justify the running time of your dynamic programming algorithm.