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?

1 answer

  • answered 2018-02-13 01:53 גלעד ברקן

    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