2016-02-10 19:06:53 UTC
looking to get home. There's a rescue truck,
11 miles away. Along the route, there is a
series of rest stations, one at each mile.
To make this long trip, you need water. You
have a wagon, which can carry up to 7 liters.
You drink one liter of water during the hike
between each station, forward or backward
Clearly, you cannot make it in one shot. However,
you may store any quantity of water at the rest
stations. Hence the solution: a series of hikes,
back and forth,dropping and picking up water, until
you ultimately arrive at the rescue point.
What is the minimum initial quantity of water required,
at the base?
This case isn't hard, as 11 miles is a short
distance. But imagine it's 20 to the rescue station,
that would be a lot of work!
Note the problem statement: not merely to find
a procedure to reach safety, but also minimizing
the store of water. So, for a long walk, you
could find an algorithm solution; but how would
you show your algorithm is optimal?