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.