How to find the longest route?

Question

The following problem:

An engine (such as a car) begins its journey along a straight road. Its consumption is directly proportional to the distance (for example, 480 km uses one unit of fuel and, therefore, 48 km uses a tenth of the fuel). This engine can transport no more than one unit of fuel.

At the starting point is the supply of fuel blocks n0. At different points of the route there are fuel depots (for example, n1 @ d1, n2 @ d2, etc.), and the driver can unload the fuel anywhere on the route. For example, with a value of 480 km for one device, the driver can move 160 km, create a depot with 1/3 units of fuel and return to the starting point for refueling its engine.

I am looking for an algorithm (or some ideas to find it) to find the maximum distance that can be reached depending on the source of fuel and the depots on the route.

Answer 1

I think you can also "invert" the comparison "<=" used in your a * method, dijkstra.

Or add a boolean parameter (best, worst).

This way you can keep the same path without re-code.

Answer 2

By intuition, the greedy algorithm should be optimal, i.e. By maximizing the amount of fuel available in each depot, you maximize the possible route. This is just my opinion, and I assume that "anywhere on the route" is "in fact in any depot."

How will the greedy algorithm work? At each point in time, you have only two decisions: “move forward” or “return to the previous depot to replenish”. The greedy will always move backward until he increases the reserve of the current reserve.