11288 - Carpool

[fernando]

Hi, this is my approach to the problem:

- Apply Dijkstra for each of the possible subsets of people into a car.
- Then i have to find disjoint-subsets (which represent people in the cars) whose union has all the people and their sum of costs (obtained by Dijkstra) is minimal.

For the second part i don't find a good algorithm to solve it, can ayone describe a good method? or a different approach to solve this problem, which seems very interesting to me, thanks.

[sclo]

The second part is NP-hard, meaning there is no good algorithm.
It is NP-hard even for the case of only 2 cars. (it is 0-1 knapsack problem)

Bitmask dp is sufficient for this problem, since n is only 15