Dyskretny problem plecakowy.
Jeden z ważniejszych i najczęściej spotykanych problemów z programowania dynamicznego. Sprowadza się do tego, że mając plecak o pojemności C i n przedmiotów, z których każdy ma określoną wagę i wartość, chcemy wybrać z nich takie, żeby ich łączna waga nie przekraczała pojemnośi plecaka i suma ich wartości była największa możliwa.
Odmiana dyskretna problemu (czyli ta, którą się zajmujemy obecnie) wyklucza możliwość dzielenia jednego przedmiotu na części.
Sposoby rozwiązania
Najbardziej oczywistym, ale i najmniej efektywnym jest algorytm sprawdzający wszystkie możliwe kombinacje wyboru przedmiotów. Jego złożoność wynosi 2n (tyle mamy podzbiorów zbioru n-elementowego).
My zajmiemy się znacznie wydajniejszymi metodami.
n - liczba przedmiotów
W[i] - waga i-tego przedmiotu
V[i] - wartość i-tego przedmiotu
B - pojemność plecaka
A[] - tablica pomocnicza przechowująca wartości z już włożonych przedmiotów
C[] - tablica pomocnicza, której aktualizacja dokona się przez dołożenie nowego przedmiotu
Metoda 1.
A[p] - maksymalna wartość plecaka o pojemności p
for i=1 to n
for p=0 to B
C[p]=max{V[i] + A[p-W[i]], A[p]};
A=C;
Główną pętlą jedziemy po wszystkich przedmiotach. Każdym z nich próbujemy poprawić wartości w tablicy C[] w następujący sposób:
Mamy dwie możliwości:
- nie bierzemy rozpatrywanego przedmiotu ze sobą, czyli zostawiamy rezultat z poprzednich przemiotów (jest w A[p])
- bierzemy rozpatrywany przedmiot, wtedy wynikiem jest wartość przedmiotu plus suma wartości z plecaka o pojemności p-W[i]. Jest tak, ponieważ mając w danym kroku plecak o pojemności p, aby dodać do niego coś o wadze W[i] musimy to W[i] miejsca wygospodarować, zatem biorąc elementy z plecaka o wadze p-W[i], wiemy, że co najmniej W[i] miejsca jest wolnego (plecak nie musi być pełny), ale jednocześnie, że wzięte z mniejszego plecaka przedmioty są dobrane optymalnie (bo ten podproblem już rozważyliśmy).
Maksimum z tych dwóch wartości jest wynikiem dla C[p].
Ostatnim krokiem jest po każdym obiegu głównej pętli przepisać tablicę C do tablicy A.
Złożoność tej metody wynosi O(n*|B|).
Metoda 2.
A[p] - minimalna waga plecaka o wartości p
SV = |V[1] + … + V[n]| - suma wartosci przedmiotów
for i=1 to SV
A[i] = INFINITY;
A[0]=0;
for i=1 to n
for p=0 to SV
C[p]=min{ W[i] + A[p-V[i]], A[p]};
A=C;
for i=SV to 0
if( A[i] <= B)
wypisz i;
przerwij pętlę;
Metoda 2. jest bardzo podobna do metody 1. Główna pętla przebiega po wszystkich przedmiotach, ale pętla wewnętrzna po wszystkich możliwych wartościach plecaka (czyli od 0 do sumy wartości). Dla danej wartości plecaka jego minimalną wagę wyznaczamy jako minimum z dwóch wartości:
- A[p] - nie bierzemy rozpatrywanego przedmiotu i pozostawiamy wagę taką, jaka była do tej pory
- W[i] + A[p-V[i]] - bierzemy przedmiot. Postępujemy w tym przypadku bardzo podobnie jak w poprzedniej metodzie, czyli: mamy plecak o wartości p, ale chcąc dołożyć do niego przedmiot musimy "zrobić miejsce na jego wartość" (podobnie jak w poprzedniej metodzie na wagę), czyli biorąc zawartość plecaka o wartości p-V[i] wiemy, że w naszym większym plecaku zostało co najmniej V[i] miejsca na wartość. Zatem do wagi przedmiotu dodajemy wagę plecaka wartości p-V[i] (gdzie jak w 1. metodzie przedmioty już są dobrane optymalnie).
Po zakończeniu głównej pętli w komórce A[i] mamy minimalną sumaryczną wagę przedmiotów jakie trzeba wziaść, żeby uzbierać towar wartości i. Zatem aby otrzymać wynik sprawdzamy od największej możliwej wartości w dół, czy waga przedmiotów potrzebnych do osiągnięcia takiej wartości zmieści nam się w plecaku. Pierwsze w kolejności przeglądania (czyli od SV w dół) i, takie że A[i] <= B jest wynikiem.
Złożoność tej metody wynosi O(n * |V[1]+ … + V[n]|).
Wybór właściwego sposobu na rozwiązanie problemu plecakowego zależy zatem od warunków zadania. Jeśli mamy duże wartości przedmiotów, a mniejsze wagi warto użyć metody pierwszej. Natomiast jeżeli mamy mniejsze wartości przedmiotów (jak w zadaniu M z Athiny) lepiej wybrać metodę drugą.
Muszkieterowie
Specyfikacja problemu:
Mamy n muszkieterów stojących na okręgu. W każdym kroku 'turnieju' losowany jest jeden, który toczy pojedynek z sąsiadem z prawej. Przegrany odpada.
Mając dane kto wygrywa z kim dla każdej pary muszkieterów, wyznacz tych, którzy przy odpowiednim losowaniu mają szansę wygrać turniej. UWAGA: Nieprawda, że jeżeli A wygrywa z B i B wygrywa z C, to A wygrywa z C. Relacja jest nieprzechodnia (czy jak się to zwie…).
Rozwiązanie:
Zastanówmy się, kiedy jakiś muszkieter może wygrać turniej. Wiadomo, że musi dojść do finału z drugim zawodnikiem i jego pokonać. Wyniki poszczególnych pojedynków już znamy, więc pozostaje wyznaczyć, czy dwaj muszkieterowie mogą się spotkać w finale. Aby do tego doszło muszą wybić wszystkich innych. Rozważmy sobie taką sytuację: mamy trzech muszkieterów. Kiedy skrajni dwaj mogą się spotkać? Ano wtedy kiedy lewy skrajny może spotkać się ze środkowym i środkowy może spotkać się z prawym skrajnym (bo pojedynki toczą się tylko w jedną stronę). Ponadto jeden ze skrajnych musi środkowego wyeliminować, aby zostali tylko oni.
Zastanówmy się jak przełożyć to na programowanie dynamiczne. Podproblemem dla nas będzie, czy, mając trzech muszkieterów, skrajni dwaj mogą się spotkać. Pierwszą, 'najmniejszą' sytuacją jest wybranie trzech kolejnych muszkieterów. Wiemy, że lewy może spotkać się ze środkowym (bo to jego sąsiad) i wiemy, że środkowy może spotkać się z prawym (sąsiad). Znamy wyniki pojedynków skrajnych ze środkowym, więc jesteśmy w stanie ten podbroblem rozwiązać. Poszerzając go o kolejnych muszkieterów rozwiązujemy problem ogólny.
Teraz mając informacje dla każdej pary czy mogą się spotkać wyznaczamy potencjalnych zwycięzców turnieju:
A, B - muszkieterowie
Jeżeli A może spotkać się z B i B może spotkać się z A (bo idziemy tylko w jedną stronę, więc A nie jest w stanie w żaden sposób doprowadzić do usunięcia muszkieterów po swojej lewej, którzy są po prawej muszkietera B, i na odwrót) to potencjalnym zwycięzcą turnieju jest zwycięzca z pary A,B.
A[i][j] - czy muszkieter i może spotkać się z j
W[i][j] - czy muszkieter i wygrywa w bezpośrednim pojedynku z j
01. for i=0 to n-1
02. A[i][(i+1)%n] = true;
03. for k=2 to n-1
04. for i=0 to n-1
05. j=i+k;
06. A[i][j%n] = false;
07. for q=i+1 to j-1
08. if( A[i][q%n] && A[q%n][j%n] && (W[i][q%n] || W[j%n][q%n]) )
09. A[i][j%n] = true;
10. for i=0 to n-1
11. for j=0 to n-1
12. if( A[i][j] && A[j][i] )
13. if( W[i][j] )
14. wygrywa i;
15. else
16. wygrywa j;
Linie 1-2: ustawiamy, że sąsiedzi mogą się spotkać.
Linie 3-5: wyznaczamy dwóch skrajnych muszkieterów
Linie 7-9: sprawdzamy wszystkich muszkieterów między skrajnymi i dla każdego sprawdzamy, czy 'za jego pomocą' może dojść do spotkania i z j
Linie 10-16: Sprawdzamy dla każdej pary muszkieterów, czy mogą spotkać się w finale i (jeżeli mogą) wyznaczamy potencjalnego zwycięzcę turnieju.
Gdyby coś było niejasne, postaram się poprawić.
obrazek: pl.wikipedia.org
