Re: Dynamic Programming Problem

From: Farhan (russoue_at_gmail.com)
Date: 03/28/05 

Date: 27 Mar 2005 22:43:16 -0800

Then, what is the solution?

Matt Timmermans wrote:
> "Diglio A. Simoni" <diglio@simoni.org> wrote in message
> news:ouFTc.27970$Kt5.1192@twister.nyroc.rr.com...
> > Suppose C(m,dist[d]) is the optimal solution to travel distance d
using m
> > gas stations
>
> That won't do, because:
>
> > Two cases arise
> > a) Buy gas at station m, in which case:
> >
> > cost = C(m-1,dist[m]) + price[m] * ( (dist[m] - dist[j]
) /
> 10 )
> > + D( dist[m] - dist[j] )
>
> You can't do that. The problem says you have to fill your tank, and
since
> the parameters of the cost function don't capture how much gas you
have
> left, you don't know how much filling your tank will cost.
>
> In fact, the number of gas stations you've used at any point is
irrelevant.
> If you could put in however much gas you liked, you wouldn't need to
use
> dynamic programming to find a solution.
>
> Since your prof asked for complexity analysis in terms of distance, I
can
> tell that he expects you to use something like C(n,i) = the minimum
price
> paid to get to dist[i] with n gallons of gas left in the tank, which
works
> just fine.
>
> You'll probably get extra marks if you expain how you can use a
different
> cost function, or just a little finesse in the implementation, to get
a
> better complexity result in terms of the number of gas stations.
>
> --
>
> Matt