Well, actually that only solves for when the # of players and events
are same, what if there're more players than events?
The recursion you describe has exponential growth rate. f(c) for some
set of P's can't really be cached, because the number of possible c's
is just are huge as exponential.
On Jan 5, 11:10 pm, Satish <[EMAIL PROTECTED]> wrote:
> We can use dynamic programming here to find out the team configuration
> with minimum time.
>
> Define a function f(P1,P2, P3,...Pn) that returns the players sequence
> (given n players for n rounds, which swimmer swims at which position)
> that would return the total minimum time.
>
> Then f() can be defined recursively as f(P1, P2, P3,... Pn) = min {T11
> + f(P2, P3,...Pn); T21 + f(P1, P3,...Pn); T31 + f(P1,
> P2,...Pn); ......}
> where Tij is the time taken by the ith player in the jth round.
>
> The above recursion can be solved in an iterative manner using
> dynammic programming.
>
> HTH,
> Satish
>
> On Jan 4, 1:45 am, hc busy <[EMAIL PROTECTED]> wrote:
>
> > 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..- Hide quoted text -
>
> > - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
