Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart
środa, 26 marca 2014
Problem plecakowy - programowanie zachłanne
Dyskretny problem plecakowy 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).
Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart
Subskrybuj:
Komentarze do posta (Atom)
Brak komentarzy:
Prześlij komentarz