ALG#6

236 Rozdział 9. Zaawansowane techniki programowania

części plecaka przeznaczonej na sery y ’ _w r < \i oraz zabrać jak najwartościowszy ładunek, tzn. zmaksymalizować funkcję £ ' _{c x} .

Aby rozważania uczynić mniej teoretycznymi, popatrzmy na konkretny przykład kilku konfiguracji danych:

wl = l6,    w2= 12,    w3=10,

cl =80.    c2=70,    c3=60.

Kilka przykładów zamieszczonych w tabelce 9-1 ilustruje różnorodność potencjalnych rozwiązań w przypadku nietrywialnej konfiguracji danych wejściowych (taka wystąpiłaby, gdyby suma w, była mniejsza od M- Czytelnik z łatwością odgadnie właściwe rozwiązanie w przypadku takiej sytuacji... ). Chwilowo spośród trzech wymyślonych ad hoc rozwiązań optymalnym jest drugie, nic nam jednak nie gwarantuje, że nie istnieją lepsze konfiguracje parametrów _v,.

Trzeba w tym miejscu być może podkreślić, że podstawowa idea, na której została zbudowana procedura żarłok, nie gwarantuje optymalności.

Tabela 9-1.

Przykładowe rozwiązania problemu plecakowego.

Lp.	(xl, x2, x3)				z: ««.
1		fii-L u 4 10		103,5	20
2		fili) 1^3 ’ 2 ’ 3y		108,3	20
3		(2 1 2^| v 3 ’ 5 ’ 3 J		107,3	19,7

Wręcz przeciwnie, w typowym przypadku otrzymane rozwiązanie¹ będzie tylko prawie optymalne!

Przy takim postawieniu sprawy można dość szybko zniechęcić się do omawianej metody... o ile nie przypomnimy sobie uwagi zawartej na samym wstępie tego rozdziału: problemy, które będziemy chcieli rozwiązywać, mogą wymusić adaptację omawianych meta-algorytmów, każda próba bezmyślnego ich stosowania spali (prawdopodobnie) na panewce.

Jeśli oczywiście istnieje!