You made it to your destination and it’s time to take in the sights! You’ve got

Question

You made it to your destination and it’s time to take in the sights! You’ve got a list of museums,
monuments, and marble sundry that you want to see. You decided that you don’t want to deal with the
hassle of a rental car, trusting instead to taxis and limos. Taxis charge a fixed rate per distance, while
limos will take you to your next 5 stops for a fixed cost, regardless of distance (but you must use the
limo for all 5 stops). Now you need to decide when you want to use a taxi, and when to use a limo.
Given a list, L, of the travel distances between your successive destinations, the taxi rate per mile, r,
and the cost of renting a limo, b, a schedule assigns either taxi or limo to each distance on the list,
with the restriction that limo assignments must be in contiguous blocks of 5. The cost of a schedule
is simply the number of limo rentals multiplied by b, plus the total distance travelled by taxi multiplied by r. Given L, r, and
b, give a polynomial-time algorithm that returns a schedule of minimum cost (note: for this question
you should show how to return the optimal sequence, not just its cost!)

Explanation / Answer

The best solution is to define three arrays, e.g. AA_COSTS[0..n], AB_COSTS[0..n], and BB_COSTS[0..n], initialize element 0 of each to 0, and initialize elements 1 and 2 according to whichever case is selected. Then, iteratively compute elements 3 to n of each using the OPT(i) recurrence. At the end, return the min of AA_COSTS[n], AB_COSTS[n], and BB_COSTS[n]. This algorithm runs in (n) time.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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