1531834456

<9.

> Techniki algorytmiczne - przybliżone i dokładne

2.2 ZMARTWIENIE KINOMANA

Kinoman dysponuje repertuarem filmów w Multikinie na dany dzień - z każdym filmem jest związana godzina jego rozpoczęcia i zakończenia. Zakładamy, że filmy są różne i kinoman chciałby obejrzeć ich możliwie jak najwięcej. W tabeli 1 są zamieszczone przykładowe godziny wyświetlania filmów. Pytanie: ile z tych filmów może obejrzeć kinoman w całości jednego dnia?

Tabela 1.

Przykładowe godziny rozpoczęcia i zakończenia filmów

Ćwiczenie 9. jaką podpowiedz dasz kinomanowi? Podpowiadamy Tobie, byś zastosował metodę zachłanną, ale sam określ, na czym ma polegać zachłanność w tym przypadku. Sprawdź swój algorytm na danych z tabeli 1.

Dość oczywistym podejściem jest wybieranie kolejnych filmów, które kończą się najwcześniej. W ten sposób kinomanowi pozostaje więcej czasu na obejrzenie następnych filmów.

Uzasadnienie, że jest to strategia optymalna, czyli możliwie najlepsza, jest dość proste. Zastosujemy rozumowanie nie wprost. Załóżmy, że istnieje inne rozwiązanie, które jest optymalne, czyli zawiera ono więcej filmów niż rozwiązanie otrzymane zasugerowaną metodą zachłanną. Przeglądamy oba rozwiązania w kolejności filmów od najwcześniejszego i zatrzymujemy się, gdy w rozwiązaniu optymalnym jest inny film niż w rozwiązaniu zachłannym. Zgodnie ze strategia zachłanną, film w rozwiązaniu optymalnym kończy się nie wcześniej niż film w rozwiązaniu zachłannym. Możemy zatem zamienić film w rozwiązaniu optymalnym z filmem w rozwiązaniu zachłannym. Przechodząc w ten sposób do końca obu rozwiązań dochodzimy do wniosku, że rozwiązanie zachłanne zawiera przynajmniej tyle filmów co optymalne, a więc jest także rozwiązaniem optymalnym.

Ćwiczenie 10. Napisz program, który dla danego repertuaru Multikina znajduje opisaną wyżej metodą zachłanną największą liczbę filmów, jakie można obejrzeć jednego dnia. Czasy rozpoczęcia i zakończenia filmów przechowuj w tablicach.

2.3 PAKOWANIE NAJCENNIEJSZEGO PLECAKA

W tym punkcie zajmiemy się rozwiązywaniem jednej z wersji problemu plecakowego. Problem ten polega na umieszczeniu w plecaku o ograniczonej pojemności możliwie najcenniejszej zawartości. W innych zastosowaniach ten problem może dotyczyć pakowania: walizek, paczek, samochodów, samolotów itp. Zakładamy, że pakowane rzeczy są niepodzielne, tzn. nie można wziąć tylko połowy jakiejś rzeczy. Na początku założymy, że każda rzecz jest dostępna w nieograniczonej ilości. Opiszmy dokładniej ten problem, podając jego specyfikację.

Ogólny problem plecakowy

Dane:    n rzeczy (towarów, produktów itp.), każda w nieograniczonej ilości:

/'-ta rzecz waży w₍ jednostek i ma wartość p.;

W- maksymalna pojemność plecaka.

Wynik: ilości poszczególnych rzeczy (mogą być zerowe), których całkowita waga nie przekracza W i których sumaryczna wartość jest największa wśród wypełnień plecaka rzeczami o wadze nie przekraczającej W.

%

KAPITAt LUDZKI