e zeszyt: Problem plecakowy

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.

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności $B$ oraz zbiór $N$ elementów $\{x_1, x_j, ..., x_N\}$ , przy czym każdy element ma określoną wartość $c_{j}$ oraz wielkość $w_{j}$ .
Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.$

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.$

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).
W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.
W przypadku, gdy problem jest rozważany przy założeniach, że

jest problemem decyzyjnym
jest dyskretny
dla każdego elementu waga równa się wartości $w_j=c_j$

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie W? Zagadnienie to nazywane jest problemem sumy podzbioru.

wtorek, 1 kwietnia 2014

Problem plecakowy

Brak komentarzy:

Prześlij komentarz