Wersja z 22:00, 7 cze 2010 (edytuj) 188.33.103.146 (dyskusja) (→‎Realizacje algorytmu: błąd w algorytmie dynamicznym) ← poprzednia edycja		Wersja z 16:53, 19 cze 2010 (edytuj) (anuluj edycję) 89.73.61.37 (dyskusja) (dyskretny to nie binary!) następna edycja →
[[Grafika:Knapsack.svg\|300px\|right\|thumb\|Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg?]] '''Dyskretny problem plecakowy''' ([[Język angielski\|ang.]] ''~~binary~~discrete knapsack problem'') jest jednym z najczęściej poruszanych [[problem optymalizacyjny\|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 <math>c_{j}</math> oraz waży <math>w_{j}</math>. 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: Różnice pomiędzy wersjami

Problem plecakowy (edytuj)