Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path is fixed (ie) you have to go from C1 to Cn through C2, C3,.. and so on. The objective is to fill fuel in these cities in such a way the spendings on fuel is minimized. I thought about storing the minimum prices within a window whose requirements add up to K and then find the minimum cost required to traverse. I'm not sure how it holds up or is it even right in the first place. What if being greedy and filling up fuel to reach the city empty till you reach the closest city with cheaper fuel, not the optimal solution? How do i prove that it is?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank).
The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this solution is in fact identical to the greedy one (to understand why this almost always works, you can read up on matroids and see how the standard proof is done in this case).
Informally, in this case :
Call GS your greedy strategy and let OPTS be an optimal strategy which agrees with GS for the longest time, starting from the beginning. Suppose GS and OPTS differ in strategy for the first time in city C:
- If OPTS fuels up more than GS at this point, then that means that GS fueled up just enough to reach the next cheapest city C'. It is clear that OPTS will arrive in C' with more fuel than GS (more than 0). But GS can then fill its tank up to as much as OPTS (for cheaper than OPTS could have at any point between C and C'). We can thus construct an optimal strategy OPTS' which does what GS does up to C' and then copies OPTS. But OPTS' is optimal and "agrees with GS" for longer than OPTS, which is impossible by definition of OPTS. So it is impossible that OPTS fuels up more than GS in C.
- If OPTS fuels up less than GS in C, then let C' be the next city where OPTS is gonna fuel up. C' can not be cheaper than C, otherwise GS would have filled up just enough to get there and OPTS would have had to fuel up at some point between C and C'. So C' is as least as expensive as C, and filling up in C would not have been worse for OPTS. We can once again construct a new strategy OPTS' which contradicts the definition of OPTS. So it is impossible that OPTS fuels up less than GS in C.
Putting both together, we see that there can not be a "first disagreement point" between GS and OPTS. Thus, GS = OPTS, and GS is an optimal strategy.
