An extension of the boat-river problem, what is the general answer ?

Правка en1, от prac64, 2018-09-01 09:15:34

The general boat river problem is that, you have a river and a boat, the boat can carry atmost 2 people at once. The objective is for all people to cross over to the other side of the river.

Each person limits the time it takes to cross the river when that person is in it. Example: if a A has a limit of 1 and B has a limit of 2 and they cross the river while in the same boat then it takes 2 minutes for them to cross i.e. max(A,B)

Now in the general problem some small number of fixed limits are given, lets say 1,2,5,6, and the minimum time for every person to cross the river is asked. In this case the answer is 13, first 1&2 go, then 1 comes back, then 5&6 go, then 2 comes back, then 1&2 go to the other side, now every one has crossed.

But what if an array of limits is given ? lets say of size 10? or 20? or 50?, how do you solve this then ? What is the complexity to solve it programatically ?

Теги puzzle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский prac64 2018-09-01 09:15:34 987 Initial revision (published)