Knapsack

Input

Finite set $U$, for each $u \in U$ a size $s(u) \in \mathbb{Z}^{+}$ and a value $v(u) \in \mathbb{Z}^{+}$, and positive integers $B$ and $K$.

Question

Is there a subset $U' \subseteq U$ such that $\sum_{u \in U'} s(u) \leq B$ and such that $\sum_{u \in U'} p(u) \geq K$?

Classes

• NP-complete

Comments

Remains NP-complete if $s(u) = s(v)$ for all $u \in U$ ([problem:subset-sum]). Can be solved in pseudo-polynomial time by dynamic programming (e.g. see (Dantzig, 1957) or (Lawler, 1976))

Proofs

NP-complete

Transformation from Partition (Karp, 1972).

Reducible from

• Partition

References

• Dantzig, G. B. (1957). Discrete-Variable Extremum Problems. Operations Research, 5(2), 266–288. https://doi.org/10.1287/opre.5.2.266
• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9