2
$\begingroup$

our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming.

In our algorithms book, there is the following problem: (an example problem for dynamic programming)

A driver has 3 cars. He wants to use all of the 3 cars, but want to use the least gas. Each car has a different engine, so it will consume different amounts of gas to get to each destination. What is the least amount of gas we can consume while still using each car? After he switches cars, he can't go back to the previous car.

Input description:

First is a number $n$, which is the number of destinations that he wants to reach. Then there are 3 lines, each is the gas consumed while trying to reach each destination (line 1 is car 1, line 2 is car 2, etc..)

Example input:

7

2 4 1 5 1 1 2

3 3 2 5 3 2 2

1 1 5 4 3 3 3

Example output:

12 (third car (2 destinations), first car (4 destinations), second car (1 destination).)

However, I can't figure out how to start, as I'm still learning DP. Could you please help me or give me any hints?

I think it's a great good example problem, because other problems are very similar so if I master this one, I should be able to solve other problems.

Thanks!

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
4
$\begingroup$

Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.

Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations).

Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that each car must be used at least once. If no feasible solution exists then $OPT[i,j] = + \infty$.

According to the above definition, you have $$OPT[1,j] = \begin{cases} g(1, c_1) & \mbox{if } j=1 \\ +\infty & \mbox{if } j>1 \end{cases}$$.

and, for $i=2, \dots, n$:

$$OPT[i,j] = g(i,c_j)+ \begin{cases} OPT[i-1, j] & \mbox{if } j=1 \\ \min\{ OPT[i-1, j], OPT[i-1, j-1] \} & \mbox{if } j>1 \end{cases}.$$

The solution to your problem is $OPT[n,3]$, which can be computed in $O(n)$ time using dynamic programming.

Improve this answer
$\endgroup$
7
  • $\begingroup$ How does it ensure that all cars have to be used? $\endgroup$
    – SomeDude
    Commented Mar 20, 2020 at 20:19
  • $\begingroup$ By definition of $OPT[n,3]$, the last car used must be $c_3$. Moreover, the first car used must necessarily be $c_1$ (since $OPT[1,j]$ is finite iff $j=1$). Finally, notice that if car $c_j$ is used to travel to the $i$-th city (with $i>1$), then the formulas ensure that car used to reach the $(i-1)$-th city is either $c_j$ or $c_{j-1}$ (if $j>1$). This means that a solution cannot use $c_1$ immediately before $c_3$, i.e., $c_2$ must be used as well. $\endgroup$
    – Steven
    Commented Mar 20, 2020 at 22:17
  • $\begingroup$ So you are imposing an order of cars to be 1, 2, 3 ? $\endgroup$
    – SomeDude
    Commented Mar 20, 2020 at 22:53
  • $\begingroup$ No, I am imposing that the order of cars is $c_1, c_2, c_3$, which is some permutation of $1,2,3$. $\endgroup$
    – Steven
    Commented Mar 20, 2020 at 22:54
  • $\begingroup$ for each permutation , you need to run the same equations right? I mean for .e.g. c1 = 1, c2= 2, c3 = 3 and then c1 = 1, c2 = 3, c3 = 2 then c1 = 2, c2 = 1, c3 = 3 etc. right? $\endgroup$
    – SomeDude
    Commented Mar 20, 2020 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.