0
$\begingroup$

There are n hotels given at a0, a1, ..., an such that 0 < a0 < a1 < ... < an. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Moreover, you are required to complete your journey in exactly d days (i.e have to make d-1 stops in between). If you travel x miles during a day, the cost for that day is x^2. You want to plan your trip so as to minimize the total cost - that is, the sum, over all travel days, of the daily cost. Find the optimal sequence of hotels at which to stop.

I came up with this dp solution:

Let dp(i) be the minimum cost such that the last stop is hotel i. Base case: dp(0)=0.

To compute dp(i), I consider all possible places 0<=k<i, that we might have stopped before. Thus, the recurrence relation becomes:

for i=1;i<=n;i++ dp(i)=inf prev(i)=undefined for k=0;k<i;k++ if (dp(i)>dp(k)+(ai-ak)^2) dp(i) = dp(k)+(ai-ak)^2) prev(i) = k

How do we make sure that this algorithm takes exactly d stops?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

For this problem, you should be using a two dimensional table where dp(i,j) is the minimum cost such that hotel i is reached in exactly j days.

If i<j there is no possible solution.

If i=j there is the solution where every hotel is visited.

If i>j, compare

  • dp(i-1,j-1) + (a(i) - a(i-1))^2
  • dp(i-2,j-1) + (a(i) - a(i-2))^2
  • ... as long as i-n>=j-1

And pick the minimum.

To find the optimal sequence, either store the previous hotel visited in the table or go back through the table starting at dp(n,d).

Improve this answer
$\endgroup$
0
1
$\begingroup$

Start with yinnosanders algorithm, then try to get faster than $O (n^3)$ in typical cases:

With your cost model, travelling a total distance of x miles in d days costs at least $x^2 / d$. If you could stop anywhere you like, you would travel $a_n / d$ miles every day.

First find a reasonably good set of stops: On each day, when there are d' days left, you pick the hotel whose distance is closest to the remaining distance, divided by d'. This gives you an upper limit L for the cost of the optimal journey.

Now jinnosanders suggests that you calculate dp(i,j). But first we calculate a lower limit for the cost of any journey that involves stopping at hotel i on day j: The cost would be lowest if you drove the same distance on each of the first j days, and the same distance on the remaining last days. The cost is at least $a_i^2 \space/\space j\space+\space(a_n - a_i)^2/(d-j)$. If this cost is higher than the upper limit L for the best solution that we found earlier, then there is no need to calculate dp (i, j) and we set dp (i, j) = infinity instead.

We will have dp (j-1, j-1) ≥ dp (j, j-1) ≥ dp (j+1, j-1) ... so when we calculate dp (i, j), we stop when dp (i-n, j-1) = infinity. This should work considerably faster than O (n^3) in typical cases if the hotels are reasonably close to equidistant.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What guarantee do you have that your upper limit calculation will result in a possible journey? It seems like you need to add the condition in paragraph 3 that a hotel can only be selected if there are at least d' hotels after it. $\endgroup$ Commented Oct 25, 2017 at 12:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.