1531834458

< 11 >

> Techniki algorytmiczne - przybliżone i dokładne

type Tablicaln =array(l..Maxn] of integer;

gdzie Maxn jest statą oznaczającą maksymalną liczbę różnych rodzajów rzeczy. Oznaczmy przez Waga pojemność plecaka W, a przez Plecak wartość całkowitej zawartości plecaka. Wtedy ilości poszczególnych rzeczy, których jest n, oznaczone przez q[i), są obliczane w następujący sposób:

Plecak:=0;

for i:=l to n do begin q[i]:=Waga div w[i];

Waga: =Waga-q [i] *wji);

Plecak:=Plecak+p[i]*q[i]

Ćwiczenie 13. Uzupełnij powyższy fragment programu do pełnego programu, służącego do wyznaczania zachłannego rozwiązania ogólnego problemu plecakowego. Sprawdź działanie swojego programu na przykładzie z tabeli 2 i porównaj wyniki z otrzymanymi w rachunkach bez pomocy komputera. Za kolejność rzeczy wybieraj kolejności odpowiadające wszystkim trzem kryteriom.

W powyższej implementacji zakładamy, że rzeczy są rozpatrywane w kolejności określonej wcześniej, a więc są już uporządkowane zgodnie z pewnym kryterium, jeśli znasz jakiś algorytm porządkowania (sortowania) i potrafisz go zaprogramować, to wykonaj następne ćwiczenie.

Ćwiczenie 14. Uzupełnij program otrzymany w ćwicz. 13 o porządkowanie rzeczy zgodnie z wybranym kryterium.

Decyzyjna wersja problemu plecakowego

Omawiana wyżej wersja problemu plecakowego jest określana jako ogólna, gdyż założyliśmy, że dysponujemy nieograniczoną ilością każdej z rzeczy. Często jednak pakując plecak mamy tylko po jednej sztuce każdej rzeczy, wtedy nasz wybór polega jedynie na podjęciu decyzji: wziąć tę rzecz, czy jej nie brać. Taka wersja tego problemu nazywa się decyzyjnym problemem plecakowym. Mimo wprowadzonego do wersji ogólnej ograniczenia na liczbę dostępnych egzemplarzy poszczególnych rzeczy, problem decyzyjny jest nadal dość ogólny, gdyż, jeśli jakaś rzecz występuje w większej ilości, to możemy każdy jej egzemplarz nazwać inaczej i wtedy każda rzecz (egzemplarz) będzie występować pojedynczo.

Ćwiczenie 15. Znajdź rozwiązania zachłanne dla decyzyjnego problemu plecakowego, dla którego dane znajdują się w tabeli 2. Czy jest wśród nich rozwiązanie optymalne, czyli możliwie najlepsze? Uzasadnij swoją odpowiedź.

Ćwiczenie 16. Zmodyfikuj program otrzymany w ćwicz. 13 tak, aby rozwiązywał decyzyjny problem plecakowy. Podobnie, w tym celu zmodyfikuj program otrzymany w ćwicz. 14, jeśli je rozwiązałeś.

2.4 NAJDŁUŻSZA DROGA NA PIRAMIDZIE

Kolejny problem ma charakter łamigłówki liczbowej. Polega on na znalezieniu takiej drogi przejścia z wierzchołka piramidy - patrz rys. 2 - do punktu w podstawie piramidy, aby suma elementów, przez które prowadzi droga, była jak największa. Droga z korzenia do podstawy powinna zawierać dokładnie jeden element z każ-