11288 - Carpool

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

11288 - Carpool

Post by 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.

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada

Post by 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

Post Reply

Return to “Volume 112 (11200-11299)”