Bin Packing

Input

Finite set $U$ of items, a size $s(u) \in \mathbb{Z}^{+}$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.

Question

Is there a partition of $U$ into disjoint sets $U_1, U_2, \dots, U_K$ such that the sum of the sizes of the items in each $U_i$ is $B$ or less?

Classes

• NP-complete

Comments

NP-complete in the strong sense. NP-complete and solvable in pseudo-polynomial for each fixed $K \geq 2$. Solvable in polynomial time for any fixed $B$ by exhaustive search.

Proofs

NP-complete

Transformation from Partition, [problem:3-partition].

Reducible from

• 3-Dimensional Matching