There are 100 girls and 100 guys.
Each Girl have their individual preference list for which guy theyâd like to marry. Each list contains all 100 boys in the order of the girlâs preference. Weâd like to match them up
as well as we can according to their preferences. To measure how well weâre doing, we assign each match a number: the number of the guy on the girlâs preference list. So if a girl gets to marry her second choice, e.g., we assign the number 2. Weâd like to keep the sum of numbers for all the matches as small as possible. What is the answer
weâll get in the WORST case ?
Brak odpowiedzi do tego tematu
Tematy podobne do: Z życia wzięte x
Kombinatoryka i prawdopodobieństwo
Paznokcie - z zycia wzięteNapisany przez Davido, 27 Jul 2011 GIMNAZJUM |
|