3
$\begingroup$

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?

  • 0
    Is dynamic programming of any help here?2012-11-30
  • 0
    -I was thinking of more of a mathematical, intuitive approach, but I do not mean non-rigorous by intuitive.2012-11-30
  • 0
    Is there a consistent strategy that yields the minimum time for all n?2012-11-30
  • 1
    [This](http://www.inf.fu-berlin.de/inst/ag-ti/uploads/tx_tipublications/Crossing_the_bridge_at_night.pdf) might be helpful.2012-11-30
  • 0
    The new URL for the document linked by @A.Schulz: [Crossing the Bridge at Night](https://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf) by Günter Rote, 2002.2016-10-11

2 Answers 2