Problem plecakowy: Różnice pomiędzy wersjami

Usunięte 31 bajtów ,  2 lata temu
m
Wycofano edycje użytkownika 217.96.169.16 (dyskusja). Autor przywróconej wersji to RoclorD.
(xDDDDD)
m (Wycofano edycje użytkownika 217.96.169.16 (dyskusja). Autor przywróconej wersji to RoclorD.)
Znacznik: Wycofanie zmian
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 [xDDDDDDDDDDDD[kombinatoryka|kombinatoryce]], [[złożoność obliczeniowa|teorii złożoności obliczeniowej]], [[kryptografia|kryptografii]] oraz [[matematyka stosowana|matematyce stosowanej]].
 
[[Problem decyzyjny (teoria obliczeń Jakuba Majerczyka)|Decyzyjna]] wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej ''C'' może być osiągnięta bez przekraczania wagi ''W''?"
 
== Definicja ==