Vtyjkyuk

I'm dealing with the following variant of the well-known Jeep problem:

A 1000 mile wide desert needs to be crossed in a Jeep. The mileage is one mile / gallon and the Jeep can transport up to 1000 gallons of gas at any time. Fuel may be dropped off at any location in the desert and picked up later. There are 3000 gallons of gas in the base camp. How much fuel can the Jeep transport to the camp on the other side of desert?

So instead of "exploring" the desert or trying to drive as far as possible, the problem here is to transport as much fuel as possible for a given distance.

I've thought about reducing this problem to the well-studied ones, but I can't come up with anything that makes sense. I don't even know how to approach this.

Any pointers?

Let's represent your starting location as $0$ and the destination as $1000$.

Let $f(x)$ be the greatest amount of fuel that can possibly be transported
to or past $x$ miles from the starting point.
For example, if you pick up $1000$ gallons, drive to $1$ (one mile), drop off $998$ gallons, drive back, repeat the trip to $1$ and back,
and on the third trip out you drive to $100$ where you drop
$801$ gallons of fuel, then you will have transported $2995$ gallons
to point $1$: the $1996$ gallons you cached there and the $999$ gallons
that were in the jeep when you passed $1$ on the third trip from $0$.

You should be able to show that for $0 leq x leq 200$,
$f(x) = 3000 - 5x$.
The intuitive reason is that you will either have to pass every point
between $0$ and $200$ five times (three times outbound and twice in the
return direction) have to abandon some fuel without using it;
and the latter strategy will deliver less fuel to points beyond where
you abandoned the fuel.

The previous example that transported $2995$ gallons to or past
point $1$ was therefore optimal, or at least was optimal up to $1$.

It follows that only $2000$ gallons can reach $200$ no matter where you
leave your caches along the way.

You should then be able to show that for
$0 leq y leq frac10003$,
$f(200 + y) = 2000 - 3y$.
Moreover, you achieve this by delivering exactly $2000$ gallons of fuel
to $200$, including the fuel in the jeep the last time you arrive
at $200$ in the forward direction,
then making sure you have $1000$ gallons in the jeep each time you
drive forward from $200$.

Finally, for $0 leq z leq 1000$,
$fleft(200 + frac10003 + zright) = 1000 - z$.
You achieve this by delivering exactly $1000$ gallons of fuel
to $200 + frac10003$ and then fully loading the jeep with any
fuel you have cached at that point and
making just one trip forward.

The answer is $f(1000)$.

Not sure this is the best, but I would:

1. load jeep up, travel 200mi, dump 600 gallons, go back to base


2. repeat step 1)


3. load jeep, go 200 mi. There is now 2000 gallons, 800mi from destination


4. travel 333 1/3mi, dump 333 1/3gallons, go back to 800mi mark.


5. load jeep, travel 333 1/3 mi. There's now 1000 gallons, 466 2/3 miles from destination


6. travel 466 2/3 miles, and you have 533 1/3 gallons left.