Transportation of Bananas

There are 2 cities A and B, dist. between them is 1000 Km
we have 3000 bananas in city A and a elephant can carry max 1000 bananas at
any given time and it needs to eat a banana every 1 Km.

How Many Max. No. of bananas one can transfer to city B?

Note : the elephant cannot go without bananas to eat.

One possible solution is to transport the banana in stages or intervals


for 200 kms we have,
A   200  B  200   C  200   D  200   E   200  F
|--------|--------|--------|--------|--------|

A to B
------
-> 2000, 800
<- 2000, 600
-> 1000, 1400
<- 1000, 1200
-> 0   , 2000

distance left = 800

B to C
--------
-> 1000, 800
<- 1000, 600
-> 0,    1400

distance left = 600

C to D
-------
-> 400, 800
<- 400, 600
-> 0,   800

distance left = 400

Move from D to F , leaving 400 bananas.


for, 250 kms we have,
A  250   B   250  C  250   D  250   E
|--------|--------|--------|--------|

A to B
------
-> 2000, 750
<- 2000, 500
-> 1000, 1250
<- 1000, 1000
-> 0   , 1750

distance left = 750

B to C
------
-> 750 , 750
<- 750 , 500
-> 0   , 1000

distance left = 500

Go directly from C to E (500 kms) leaving 500 bananas

for, 300, we have
A   300  B  300   C  300   D  100   E
|--------|--------|--------|--------|

A to B
-------
-> 2000, 700
<- 2000, 400
-> 1000, 1100
<- 1000, 800
-> 0,    1500

distance left = 700

B to C
------
-> 500, 700
<- 500, 400
-> 0  , 600

distance left = 400

travel C to E, leaving only 200 bananas

Using the above scheme, we can transport a max of 500 bananas for intervals of 250, 
this is probably not the best solution, and using dynamic programming we can find the
best solution.