A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time.
The problem is: you have to travel $1000$ km. The only gas station is at the starting point. Your maximum fuel tank capacity is just enough for $50$ km traveling, you are allowed to "bury" fuels in the middle of the journey and save it for later.
For example you can travel $20$ km first, and bury $10$ km worth of fuel there, and then go back to refuel, so next time you can retrieve the $10$ km fuels you left and reach further with it.
You need to find the most efficient way to reach the destination.
What I thought of is using dynamic programming, however you have to assume the distance you travel before each time you do refueling is an integer in terms of kilometers, else you it is hard to do it with DP, I have not try linear programming yet, but I think it is possible.
Do you have any idea how to do it? Or any hints?
Most importantly what type of cs problem is it? is it NP hard? Is it solvable by machine or is it more of a mathematical problem?
Some more thoughts:
- Since it is a continuous path, asking whether if it is NP might be bit silly, but I am still very curious.
- $1000$ and $50$ might be deliberately picked to avoid complex computation.
- Is there a greedy solution? I cannot think of any just yet.
- I now think it more of a mathematical pattern finding problem, though my friend claims it is a cs problem, so I am decide to keep this post.
And if you have any scientific articles or textbooks related to this please tell me, I do not know where to start in the first place.