Gas tank capacity: 15 Gallons

 

 

Case 1

 

Initially no gas in the tank

 

Station  Si 

Pi: Gas price per gallon at station Si

Gi  :Number of gallons needed to go from Si to Si+1

 

S0

$3

1

S1

$1

5

S2

$6

2

S3

$2

13

S4

 

 

 

 

In this case, the optimal refueling policy is shown below with a total fuel cost of $3*1 + $1*15 + $6*0 + $2*5=$28:

                 

                 

Station  Si 

Fi: gallon purchased at station Si

Number of gallons when leaving Si

 

S0

1

1

S1

15

15

S2

0

10

S3

5

13

S4

0

 

           

 

 

 

 

 

Case 2

 

Initially no gas in the tank

 

Station  Si 

Pi: Gas price per gallon at station Si

Gi: Number of gallons needed to go from Si to Si+1

 

S0

$3

1

S1

$2

5

S2

$6

2

S3

$1

13

S4

 

 

 

 

In this case, the optimal refueling policy is shown below with a total fuel cost of $3*1 + $2*7 + $6*0 + $1*13=$30:

                 

                 

Station  Si 

Fi: gallon purchased at station Si

Number of gallons when leaving Si

 

S0

1

1

S1

7

7

S2

0

2

S3

13

13

S4

0