ALG#5

9.2. Algorytmy żarłoczne, czyli... 235

w przeciwnym wypadku zwróć „nie ma rozwiązania

)

W opisie metody zostały użyte następujące oznaczenia:

W

ROZW

X

-    zbiór danych wejściowych;

-    zbiór, na podstawie którego będzie konstruowane rozwiąza

nie;

element zbioru;

Wybór(A)

OdpowiadaOK)

Znalesiono(R)

-    funkcja dokonująca „optymalnego” wyboru elementu ze

zbioru A (usuwając go z niego);

-    czy wybierając Xmożna tak skompletować rozwiązanie

cząstkowe, aby odnaleźć co najmniej jedno rozwiązanie globalne?

-    czy /? jest rozwiązaniem zadania?

Powyższy zapis wyjaśnia nazwę metody: na każdym etapie dobieramy najlepszy kąsek, nie troszcząc się specjalnie o przyszłość... Popatrzmy na kilka przykładów zastosowania nowej metody.

9.2.1 .Problem plecakowy, czyli niełatwe jest życie turysty-piechura

Wczujmy się teraz w rolę turysty wybierającego się na dłuższą pieszą wycieczkę po górach. Aby urealnić przykład, niech naszym zadaniem będzie dotarcie na szczyt pewnej góry w Pirenejach, gdzie znajduje się „punkt zbiorczy”, który nasi wspólni znajomi wybrali na zorganizowanie „przyjęcia” na łonie natury. Do punktu docelowego zmierza w sumie pięć osób - każda z nich zobowiązała się dostarczyć imponującą ilość wiktuałów, tak aby umówioną imprezę uczynić iście królewską ucztą. Nie będziemy wnikać w zbędne szczegóły usiłując odgadnąć, co niosą ze sobą pozostałe cztery osoby, zajmiemy się jedynie naszym prywatnym problemem, który napotkaliśmy przygotowując wyprawę. Załóżmy, żc zostaliśmy obarczeni zadaniem dostarczenia kilku gatunków dobrych serów i niespecjalnie wiemy, jak upakować je w wolnej przestrzeni plecaka.

Nasz plecak posiada gwarantowaną przez producenta pojemność 60 litrów, z czego zostało nam M=20 litrów na część kulinarną. Reszta już jest wypełniona niezbędnymi do przeżycia w górach elementami, pozostał nam jedynie dylemat optymalnego wypełnienia reszty plecaka. Chcemy wziąć w sumie trzy gatunki sera (sl, s2 i .vj). W domowej lodówce owe sery znajdują się w ilościach wl, w2 i w3 litrów. Każdy z serów jest doskonały, niemniej możemy im przypisać orientacyjne ceny cl, c2 i c3. które pozwalają ustawić je w swoistym rankingu jakości. Naszym celem jest wzięcie z każdego gatunku sera takiej jego ilości (0 <xl, x2, x3 < /), aby w sumie nie przekroczyć maksymalnej pojemności