0-1 Knapsack Problem

Study Notes

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.

Description

Rozwiąż quiz, który dotyczy problemu plecakowego 0-1, polegającego na znalezieniu optymalnego sposobu pakowania przedmiotów o określonych wagach i wartościach do plecaka o ograniczonej pojemności. Quiz oparty na materiałach z RAIK 283, Data Structures & Algorithms, Dr. Ying Lu.