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 |
|