|
|
вернуться в форумExplanation Послано Denis 21 янв 2008 02:41 Some helpful description can be found at http://mathworld.wolfram.com/JeepProblem.html But i still do not understand one thing : For example, the farthest a Jeep with n==1 drum can travel is obviously 1 unit. However, with n==2 drums of gas, the maximum distance is achieved by filling up the Jeep's tank with the first drum, traveling 1/3 of a unit, storing 1/3 of a drum of fuel there, and then returning to base with the remaining 1/3 of a tank. At the base, the tank is filled with the second drum. The Jeep then travels 1/3 of a unit (expending 1/3 of a drum of fuel), refills the tank using the 1/3 of a drum of fuel stored there, and continues an additional 1 unit of distance on a full tank, giving a total distance of 4/3. How this logic works with n==3 ??? Re: Explanation I'd like to know as well... Re: Explanation I'll try to explain... Suppose fuel tank capacity = 1 unit and we have 3 units of patrol at point A. There will be three parts of the path with lengths 1/5, 1/3 and 1. A--1/5--B------1/3------C---------------1---------------D 1. Let's carry 2 units of patrol from A to B. It would take 3 trips. Step 0: Fuel(A) = 3, Fuel(B) = 0. Step 1: Fuel(A) = 2, Fuel(B) = 3/5. Step 2: Fuel(A) = 1, Fuel(B) = 6/5. Step 3: Fule(A) = 0, Fule(B) = 10/5 = 2. And we are at B now. 2. Let's carry 1 unit of patrol from B to C. It would take 2 trips. Step 0: Fuel(B) = 2, Fuel(C) = 0. Step 1: Fuel(A) = 1, Fuel(B) = 1/3. Step 2: Fuel(A) = 2, Fuel(B) = 3/3 = 1. And we are at C now. 3. Let's carry 1 unit of patrol from C to D. It would take only 1 trip. So if we have 1-unit fuel tank and 3 litres of patrol we can travel for 1+1/3+1/5 = 23/15 km. Good luck! Re: Explanation when n == 1 we can travel 1 unit. when n == 2 we will carry 1 drum as far as I can, so the situation is as same as n == 1, we can spend the extra 1 drum of gas on the way for 3 times (carry 1 , go , left some, back ,carry 1, go), so I can travel 1/3 for the best solution when n == 3 we will carry 2 drums of gas as far as I can, then it became situation #2 , the extra 1 drum of gas will use 5 times (go , back ,go , back ,go) ,so best solution is 1/5 and so on hope this help Re: Explanation You should just try to think how far you are able to move with m, 2m, 3m liters of fuel. Then it'l be easy to reform the task as moving k * m liters at the distance n1. (k is integer and n1 < m) Re: Explanation Thank you for the explanation, everything is clear now. |
|
|