Problem plecakowy: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian |
Wycofano ostatnią zmianę treści (wprowadzoną przez 212.182.71.101) i przywrócono wersję 38210673 autorstwa Uzyj |
||
Linia 1:
[[Plik:Knapsack.svg|thumb|300px|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.]] ''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).
Podobny problem pojawia się często w [[kombinatoryka|kombinatoryce]], [[złożoność obliczeniowa|teorii złożoności obliczeniowej]], [[kryptografia|kryptografii]] oraz [[matematyka stosowana|matematyce stosowanej]].
[[Problem decyzyjny (teoria obliczeń)|Decyzyjna]] wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej ''C'' może być osiągnięta bez przekraczania wagi ''W''?"
== Definicja ==
| |||