A puzzle that involves arranging objects optimally in order to fit in a specified space.
'Packing problems' are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. Usually, the goal is either to pack a single container as densely as possible, or to pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual 'covering' problem, which asks how many of the same objects are required to cover every region of the container completely, where objects are allowed to overlap.
In a packing problem, you are given:
- 'Containers' (usually a single two- or three-dimensional convex region, or an infinite space).
- A set of 'objects', some or all of which must be packed into one or more of the containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly.
Usually, the packing must be achieved without overlaps between goods and other goods or the container walls. In some variants, the aim is to find the configuration that packs a single container with the maximal density. More commonly, the aim is to pack all the objects into as few containers as possible. In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.