Given a finite set U, for each u element U a size s(u) element Z^+ and a value v(u) element Z^+, and positive integers B and k, the knapsack problem asks if there is a subset U'⊆U such that sum_(u element U')s(u)<=B and such that sum_(u element U')v(u)>=k.

status | proved NP-complete proof date | 1972 (53 years ago) prover | Richard Karp

NP complete problems | NP problems | mathematical problems | solved mathematics problems