Generalizing this flashlight puzzle

Question

My friend told me a riddle yesterday: four people want to cross a bridge. They each will take $1$, $2$, $5$, and $10$ minutes respectively to cross the bridge. They can go across the bridge in groups of $2$, which will move as fast as the slowest person. However, they must also travel with a flashlight to not get eaten by the bridge troll. The group only has one flashlight, so after each crossing, someone must return across the bridge with the flashlight.

Question: What's the minimum time to cross the bridge?

Naively, you would send $1$ as the "chaperogne", in which case it takes $19$ minutes. However, there's a better solution. Send $1$ and $2$ together, send $1$ back, $5$ and $10$ together, $2$ back, $1$ and $2$ together, for a total of $17$ minutes.

There have been questions about this riddle on here before - my question is, can this be generalized? Formally, given a finite sequence of positive naturals $a_n$ corresponding to the "bridge-crossing times", is there a way to determine the optimal plan for getting across the bridge?

I suspect this is related to graph theory, which is definitely not my area.

Answer 1

If you can prove (and I think it's true) that it never makes sense to send back two people, then the number of people remaining to make the trip (after an out-and-back-pair) decreases over time.

Once you know that, the problem becomes amenable to a dynamic programming (or memoization) approach, much like the knapsack problem and others like it. My rough intuition (from having taught the memoization approach to knapsack a few times over the years) is that this approach is likely to be slow and require lots of memory if many of the "times" are similar, and faster and less memory-hungry if the times differ by a lot (e.g., factors of 2).