Zastosowanie programowania zachłannego

Dyskretny problem plecakowy (ang. discrete knapsack problem) 

- jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart  oraz waży . Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Decyzyjna wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej C może być osiągnięta bez przekraczania wagi W?"

Zachłanny algorytm, którego użycie w tym problemie wydaje się interesującą strategią, działa w kilku krokach:

• Najpierw szereguje przedmioty w kolejności nierosnącej, gdzie elementem porównawczym jest stosunek wartości przedmiotu do jego masy (sortowanie nierosnące względem wartości  - cena za jednostkę masy)
• Następnie metoda zachłanna próbuje umieścić w plecaku wpierw przedmiot o największej wartości k, potem kolejne rzeczy stojące za nim na posortowanej liście przedmiotów
• Gdy okaże się, że pewien przedmiot nie może zostać zapakowany do plecaka ze względu na przekroczenie pojemności, to jest on pomijany i następuje próba umieszczenia kolejnych przedmiotów aż do całkowitego wyczerpania miejsca w plecaku lub do momentu, kiedy nie będzie możliwe jakiekolwiek dodanie do plecaka przedmiotu jeszcze niezapakowanego – ze względu na przekroczenie ograniczenia.

Na poniższym schemacie przedstawimy rozwiązanie naszego przykładu metodą zachłanną:

Programowanie dynamiczne

Jak zapewne dobrze pamiętacie, sposób formułowania metod opartych na programowaniu dynamicznym został omówiony we poprzedniej lekcji. W skrócie polegał on na znalezieniu rekurencyjnych zależności między rozwiązaniami podproblemów różnego poziomu, a następnie na rozwiązywaniu coraz większych zadań i wykorzystania ich wyników do otrzymania głównego rozwiązania. Ten rodzaj algorytmów bardzo dobrze się zachowuje przy rozwiązywaniu wielu problemów optymalizacyjnych. Nie inaczej jest w przypadku problemu plecakowego.

W przypadku rozwiązywaniu zagadnienia upakowania przedmiotów potrzebna nam będzie dodatkowa tablica na przechowywanie cząstkowych wyników podproblemów – określmy ją jako P(i,j). W tablicy tej zapisywane będą mianowicie wartości optymalnych rozwiązań problemu upakowania, który będzie ograniczony do wyboru jedynie spośród pierwszych i przedmiotów, a pojemność plecaka będzie wynosić j. W trakcie rozwijania algorytmów zajmujących się upakowaniem plecaka opracowano wzór rekurencyjny na wartość P(i,j), który we sztandarowy sposób prezentuje możliwości programowania dynamicznego.

Otóż wartości tablicy P są obliczane zgodnie z poniższą zasadą:

Wytłumaczenie tego wzoru rekurencyjnego jest stosunkowo przejrzyste. Jeśli chcemy dodać do rozwiązania i-ty element, który jest cięższy od dopuszczalnej pojemności plecaka, to ten ruch jest automatycznie kwalifikowany jako nieopłacalny i nadal rozwiązanie optymalne składa się z przedmiotów o numerach 1..i-1. Natomiast jeżeli przedmiot i-ty, który zaczyna być w tej chwili brany pod uwagę, ma masę nie większą niż dopuszczalna „ładowność” plecaka, to porównujemy dwa przypadki:

1. optymalny podzbiór elementów zawiera element i-ty
2. optymalny podzbiór elementów nie zawiera elementu i-tego

Pierwszy przypadek jest opisany przez drugi parametr funkcji max w powyższym wzorze – do rozwiązania podproblemu z poprzedniego kroku dodajemy wartość ceny przedmiotu i-tego, a dostępną pojemność plecaka dla (i-1) przedmiotów zmniejszamy o tyle, ile miejsca w plecaku zajmuje przedmiot i-ty (czyli w_i).

Z wiadomych względów P(i,0) oraz P(0,j) są równe 0. Aby znaleźć całościowe rozwiązanie musimy wyznaczyć wartość P(n,W) – korzystając z rozwiązań najmniejszych podproblemów (właśnie tych o postaci P(0,x) lub P(y,0)), przechodząc do coraz większych i ostatecznie do P(n,W).

Skoro już omówiliśmy aspekt teoretyczny rozwiązywania problemu 0-1 knapsack przy zastosowaniu programowania dynamicznego, to możemy spróbować rozwiązać problem z rysunku znajdującego się na początku podrozdziału. Jak wiemy, należy odpowiednio przeliczyć wartości funkcji P – poniższe „drzewo rekurencji” pokazuje zależności między problemami i ich podproblemami – najpierw obliczamy wartości znajdujące się na samym dole drzewa, a następnie kroczymy z obliczeniami w górę, ostatnim kroku obliczając P(5,25).

Problem wydawania reszty 

– zagadnienie z dziedziny algorytmiki, problem polegający na wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są wykorzystywane w automatach z napojami, bankomatach itd.

Dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł?

Rozwiązanie

Poniżej pokazano dwa popularne rozwiązania tego problemu dla wariantu problemu, w którym zakłada się dostępność dowolnej liczby monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego.

Niech:

k – żądana kwota; wg przykładu 13

n – największy element zbioru nominałów

x – liczba potrzebnych monet; początkowo 0

Algorytm zachłanny

Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych, jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).

W tym przypadku, algorytm będzie wartość:

k – w każdym kroku pomniejszał o n

n – porównywał z wartością k, by stwierdzić, czy jest ona mniejsza lub równa

x – w każdym kroku zwiększał o 1

Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.

Dla powyższego przykładu algorytm zadziała następująco:

k	13	8	3	1
n	5	5	2	1
x	1	2	3	4