At risk of stating the incredibly obvious, or giving away answer to a fun interview question.
The naive but correct algorithm that gives the solution will have tried every combination M of K swimmers in M events. which will give you K!/(K-M)! arrangements, and the algorithm would then compare the timing and chose the best arrangement. Anything better than that? Does allowing any swimmer to swim up to M events at same performance level make this problem harder? What about fractional event? (allow relay so that more than one swimmer can swim in one event)? On Jan 1, 1:19 am, Arikan <[EMAIL PROTECTED]> wrote: > Hi, i hope you can help me with this problem? > > A coach is putting a relay team together for a 400-meter relay. > Each swimmer must swim 100 meters of breaststroke, backstroke, > butterfly, or freestyle. > > !There are at least four swimmers > > Is there a algorithm to find the optimum solution to minimize the > team's time? > (similar to dynamic programming solution for knapsack problem!) > > for example(5 swimmers): > 1 2 3 4 > 1 30 34 26 29 > 2 31 37 31 36 > 3 32 29 41 40 > 4 29 40 37 31 > 5 33 32 35 24 > > first i thought i can solve this problem with the hungarian algorithm, > but that's out of the question.. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
