There is the usual question of some men on a boat- various men have various speeds, the boat has a capacity of 2 men, and the boat takes on the speed of the slowest man in the boat at any given time. Suppose we had $n$ men and 1 canoe with a capcity of two men, with the $nth$ man taking $2^n$ minutes to cross from one side to the next. What is the strategy to optimize the time to get all men to the other side?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Given the base case: $F(2)=2$ and $F(3)=2+1+4=7$.
And given that if you have $k$ man using the following greedy strategy:
For example, for $4$ men: take $1$ and $2$ to the other side; come back with $1$; go to the other side with $3$ and $4$; go back with $2$; solve the sub-problem for $2$ men, that is just a trip of $1$ and $2$ for a total of $2+1+8+2+2=15$ time units.
This strategy is optimal (you never waste a transport), and for the time required this recursion holds: $F(n) = 2^k + 5 + F(n-2)$ (with the base case $F(3)=7$ and $F(4)=15$).
for two persons (speeds 2,4) - ans 4 mins
for 3 persons (speeds 2,4,8) - ans 2,4 go -> 4 ,2 comes back. next 2,8 go-> 8 so total 4+2+8
By Generalisation optimised time would be (2^2+2^3+......+2^n)+2*(n-2)