# amusement park scheduling rides using dynamic programming

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 ri minutes and all times are measured in integer minutes.

I tried solving it using a method similar to 0 1 knapsack problem. But the Table W which contains the waiting time for ride i varies wrt to time t. Is it exactly a knapsack plus activity selection combined problem?

Would this make any sense? Let `f(t)` represent the most achievable rides at time `t`. Then:

``````// Higher t is back in time
// since t is how many minutes
// before the park closes

f(t) = max(
// Not taking any ride
f(t - 1),

// Take ride i
1 + f(t - W(i, t) - r_i)
)
for all i
``````