Algorytm rozwiązujący zagadkę Opcje

[Fifi209]

Przeglądając forum, natknąłem na stary temat z zagadkami i jedną sobie skopiowałem:

Cztery osoby (nazwijmy je: Adam, Basia, Celina i Dorota) wybrały się samochodem na imprezę.
Rozpętała się burza, parking jest dość oddalony od domu, a okazało się, że w samochodzie jest tylko jeden parasol!
Adam idzie z parkingiu do domu - 1 minutę, Basia - 2, Celina - 5, a Dorota - 10.
Pod parasolem mieszczą się naraz dwie osoby, a gdy idą, szybsza dostosowuje swe tempo do wolniejszej (czyli Adam z Dorotą szliby 10 minut).
Aby nikt nie zmókł, wymyślili, że najpierw pójdzie Adam z Basią, Adam wróci z parasolem, potem Adam z Celiną, Adam wróci z parasolem, w końcu Adam z Dorotą. W sumie 2+1+5+1+10= 19 minut.
Sposób niezły, ale istnieje lepszy - da się to zrobić w 17 minut.
Pytanie: jak?

Z tekstu wynikają pewne założenia:

1. Prędkość osób
Adam - 1 minut
Basia - 2 minuty
Celina - 5 minut
Dorota - 10 minut

2. Parasol - mieszą się pod nim naraz maksymalnie dwie osoby
3. Miejsca:
a) Samochód
(IMG:style_emoticons/default/cool.gif) Dom

3. Osoba szybsza dostosowuje tempo do wolniejszej

Zadanie: Napisz program, który rozwiąże zagadkę korzystając z wytycznych.

Prosty zarys algorytmu jaki ja wymyśliłem:

[PHP] pobierz, plaintext 
$People = array(
	'Adam' => 1,
	'Basia' => 2,
	'Celina' => 5,
	'Dorota' => 10
);
[PHP] pobierz, plaintext 

Dwie tablice:

[PHP] pobierz, plaintext 
$Car = array();
$House = array();
[PHP] pobierz, plaintext 

Algorytm:
< Uruchomienie pętli >

• Przepisanie tablicy People do Car
• Wylosowanie dwóch osób, zapisanie ich imion do zmiennych pomocniczych i ich szybkości [i usunięcie ich z tablicy Car]
• Obliczenie, prędkości poruszania się osób - czyli sprawdzenie, która jest wolniejsza
• Dodanie czasu: prędkość wolniejszej osoby
• Dodanie osób do tablicy House
• Wylosowanie jednej osoby z tablicy House, która wróci do samochodu i dodanie jej do tablicy Car
• Dodanie czas: prędkość osoby wracającej
• Powtórzenie pętli, póki są osoby w samochodzie

Zapisanie kroków - kto i w jakiej kolejności
Porównanie czasu, jeżeli mniejszy od poprzedniego to przepisujemy kroki i zapisujemy czas
<Powrót do początku pętli>


Ja wymyśliłem taki algorytm... Jeszcze do końca nie wyszło mi napisanie tego, bo minimalny czas uzyskuję 19 minut - ale to błąd w moich wcześniejszych założeniach co do losowania.

Jestem ciekawy, czy można zrobić to jakoś bardziej optymalnie.