Mariusz Redwanz

Algorytm 2-względnie przybliżony dla problemu worka świętego Mikołaja

Problem worka świętego Mikołaja polega na upakowaniu worka prezentami w taki sposób, aby suma wartości prezentów się w nim znajdujących była jak największa. Przy czym wartość prezentu podyktowana jest jego rozmiarem a worek ma ograniczoną pojemność. Problem ten jest odmianą problemu plecakowego, w którym wartość przedmiotu jest równa jego wielkości.

Zadanie polega na znalezieniu algorytmu 2-względnie przybliżonego, tzn. dającego rozwiązanie nie mniejsze niż ½ optymalnego rozwiązania przy założeniu KP(0-1) – prezent umieszczamy w worku lub nie.

Rozwiązanie 1

Przyjmujemy, że istnieje co najmniej jeden prezent i wszystkie prezenty są mniejsze od rozmiaru worka.

Algorytm Santa Claus

1. Posortuj prezenty malejąco według wielkości

2. Zabierz kolejny (największy z pozostałych) prezent

3. Jeśli jest miejsce na dany prezent w worku to:

4. Wrzuć go do worka

5. Jeżeli zostały prezenty to wróć do punktu 2

6. Zakończ algorytm

Algorytm posiada własność stopu, ponieważ zakończy się, gdy kolejny prezent nie zmieści się w worku lub gdy wszystkie prezenty zostaną w nim umieszczone.

Dowód poprawności algorytmu:

W – wartość worka

A – zbiór prezentów umieszczonych w worku przed zakończeniem działania algorytmu

OPT = ∑ (a_i ϵ A) size (a_i)

OPT ≤ W

OPT/size(A) ≤ W/size(A)

Jeżeli istnieje prezent większy od połowy pojemności worka to rozwiązanie jest gorsze od optymalnego o mniej niż połowę. Jeżeli taki prezent nie istnieje to mamy dwie możliwości – suma wielkości prezentów jest mniejsza od połowy pojemności worka lub jest większa bądź równa połowie pojemności worka. W drugim przypadku rozwiązanie jest lepsze niż ½ optymalnego rozwiązania. W pierwszym przypadku, aby rozwiązanie to nie było 2-względnie przybliżone musiałby nie zostać włożony do worka prezent o wielkości większej od połowy pojemności worka, co jest nieprawdą gdyż największe prezenty wkładane są w pierwszej kolejności.

Rozwiązanie 2

Algorytm prezenty

1. Posortuje prezenty rosnąco według wielkości

2. Weź kolejny prezent (najmniejszy z pozostałych)

3. Jeżeli jest miejsce na dany prezent to:

4. Umieść go w worku

5. Wróć do punktu 2

6. Zakończ algorytm

Wynikiem działania algorytmu prezenty jest zbiór prezentów o łącznej wielkości nieprzekraczającej wielkości worka. Algorytm ma własność stopu – w przypadku, gdy kolejny prezent nie mieści się w worku przechodzimy z punktu 4 do punktu 6 i kończymy algorytm.

Algorytm NajwiększyPrezent

1. Posortuj prezenty malejąco według wielkości

2. Weź kolejny prezent (największy z pozostałych)

3. Jeżeli jest miejsce na dany prezent to:

4. Umieść go w worku

5. Zakończ algorytm

6. Wróć do punktu 2

Wynikiem jest prezent o największej wielkości (wartości) nieprzekraczającej wielkości worka.

Wynikiem jest najlepsze z dwóch rozwiązań (algorytmu prezenty i NajwiększyPrezent), tzn. to, w którym suma wartości prezentów jest większa. Algorytm ten jest 2-wzglednie przybliżony.

Przykład:

Worek ma pojemność równą 30. Mamy prezenty o wielkości/wartości kolejno: 3, 14, 21, 70, 2, 15, 2, 14, 7 i 5. Optymalnym rozwiązaniem jest 30 (14 + 7 + 2 + 2 + 5). Wynikiem algorytmu prezenty jest zbiór: 2, 2, 3, 5, 7 (suma 19) a algorytmu NajwiększyPrezent 21. Rozwiązaniem jest max(19, 21), czyli 21. Jest to rozwiązanie ok. 1,43 razy gorsze od optymalnego.

Dowód poprawności algorytmu:

1. Załóżmy, że wszystkie przedmioty mają rozmiar mniejszy lub równy W (jeżeli są jakieś większe prezenty to i tak nie mają one znaczenia dla dopuszczalnych rozwiązań).

2. Niech a będzie sumą uporządkowanych rosnąco elementów, które zmieściły się w worku (algorytm prezenty).

3. Niech b będzie pierwszym elementem, który nie zmieścił się w worku (algorytm prezenty).

4. Niech c będzie największym prezentem możliwym do umieszczenia w worku (algorytm NajwięszkyPrezent).

a + b > W > OPT

a + b > OPT

c ≥ b

a + c > OPT

Prawa strona jest mniejsza od sumy obu rozwiązań rozważanych przez algorytm. Ponieważ algorytm wybiera lepsze z nich jego wartość musi być większa od ½ OPT.