0-1 Knapsack Problem

Problem plecakowy

• Problem plecakowy polega na maksymalizacji wartości przedmiotów umieszczonych w plecaku o ograniczonej pojemności.
• Przedmioty mają określone wagi i wartości, które należy optymalnie dobrać.

Nazwa „0-1”

• Problem plecakowy nazywany „0-1” odnosi się do dwóch możliwości: wybrać przedmiot (1) lub go nie wybrać (0).
• Oznacza to, że każdy przedmiot może być wybrany tylko raz lub wcale.

Proponowana metoda

• Proponowana metoda do rozwiązania problemu plecakowego opiera się na dynamicznym programowaniu.
• Algorytm ten tworzy tablicę, aby śledzić maksymalne możliwe wartości dla różnych wag plecaka.

Czas działania algorytmu

• Czas działania bezpośredniego algorytmu do rozwiązania problemu plecakowego wynosi O(nW), gdzie n to liczba przedmiotów, a W to pojemność plecaka.

Zrozumienie problemu 0-1

• Stwierdzenie „problem plecakowy jest problemem 0-1” oznacza, że decyzje są binarne: można wziąć przedmiot lub go odrzucić, co sprawia, że problem jest trudniejszy do rozwiązania.

Oczekiwana wysokość drzewa BST

• Oczekiwana wysokość drzewa BST (Binary Search Tree) wynosi O(log n) przy losowym wstawianiu elementów.

Operacje wspomagane przez BST

• Drzewo BST wspomaga operacje takie jak: wstawianie, usuwanie oraz wyszukiwanie elementów, które są wykonywane efektywnie.

Przechodzenie drzewa – postorder

• Przechodzenie drzewa metodą postorder polega na odwiedzaniu najpierw lewego poddrzewa, potem prawego, a następnie samego węzła.

Wartości wypisywane w kolejności posortowanej – inorder

• Podczas przechodzenia drzewa metodą inorder wartości są wypisywane w kolejności rosnącej, odwiedzając najpierw lewe poddrzewo, następnie węzeł, a potem prawe poddrzewo.

Klucze wypisywane podczas preorder

• W przechodzeniu drzewa metodą preorder wypisywane są klucze zgodnie z kolejnością: węzeł, następnie lewe poddrzewo, a na końcu prawe poddrzewo.