There are 2 cities A and B, 1000 Kms apart. We have 3000 bananas in city A and a elephant, which can carry max 1000 bananas at any given time. The elephant needs to eat a banana every 1 Km.
How many maximum number of bananas can be transferred to city B?
Note: The elephant cannot go without bananas.
Also solved to generalized problem.
Generalized Question:
There are 2 cities A and B, 'D' Km apart. We have 'N' bananas in city A and a elephant, which can carry max 'C' bananas at any given time. The elephant needs to eat 'F' banana every 1 Km.
Write a program that will compute 'X', the maximum amount of bananas that can be transported from city A to city B.
Answer:
First, realize that if you take 1000 bananas and walk 1000 kilometers, you arrive with no banana at all. And the elephant is stuck in city B as there is no banana left for return journey. So the elephant needs to travel shorter distances or we can say that we need to subdivide distances.
How can we subdivide distances?
If we subdivide distances for each kilometer. Notice if elephant wants to shift all the bananas 1 km, you will loose 5 bananas every km. Lets see how.
- In 1st trip, elephant will pick 1000 bananas, eat one at 1 km mark, leave 998 bananas at 1 km mark and keep 1 with him for return journey.
- In 2nd trip, elephant will pick next 1000 bananas, eat one at 1 km mark, leave 998 bananas at 1 km mark and keep 1 with him for return journey.
- In 3rd trip, elephant will pick next 1000 bananas, eat one at 1 km mark, leave 999 bananas at 1 km mark. This time, he doesn't need to keep anything for return journey.
So we transferred 2995 (998+998+999) to one km distance. This process (loosing 5 bananas per km) will continue until we reach a point where we have one less round trip. In this example, that transit point will come after 200 km, when we will have 2000 bananas left with remaining distance of 800 km.
Also note that the rate of consumption remains constant no matter how we subdivide the distance, as long as the number of trips required is the same.
So in place of shifting bananas every km, we can transferred the banans 200 kilometers at once.
- In 1st trip, elephant will pick 1000 bananas, eat 200 till 200 km mark, leave 600 bananas at 200 km mark and keep 200 with him for return journey.
- In 1st trip, elephant will pick next 1000 bananas, eat 200 till 200 km mark, leave 600 bananas at 200 km mark and keep 200 with him for return journey.
- In 3rd trip, elephant will pick next 1000 bananas, eat 200 till 200 km mark and leave 800 bananas at 200 km mark. This time, he doesn't need to keep anything for return journey.
In this way, we are now left with 2000 bananas and 800 kms to go.
Now if you calculate, we will consume 3 bananas per km till next transit point. And what will be the next transit point. It should be when we are left with just 1000 bananas. This means that it will come after 333.33 (1000/3) kms.
Finally, we have 1000 bananas and 466.67 kms left. Since elephant can carry 1000 bananas at once, it will pick all 1000 bananas and reach the end with 533.33 (1000 - 466.67) bananas left. (Assumed that elephant eats the banana evenly in fractions of 1km as well.)
Generalized Answer:
So we have seen that if we have (Cn + y) where n is an integer and 0<y<=C at any point in time, our cost of walking each km is (2n+1). And from next transit point this rate will become (2n-1). We need to choose transit points such that we reduce one round time every time. In this manner, transit point will come when remaining bananas are integer multiple of C. Now you have a subset of bananas and distance left. You can apply the same process on remaining values.
This recursion will converge, when remaining bananas are less then or equal to C. (So that we can transfer all of them in single trip.)
Read full article from Dynamic programming
No comments:
Post a Comment