Packing problems

Part of a series on
Puzzles
Types Guessing Riddle Situation Logic Dissection Induction Logic grid Self-reference Mechanical Combination Construction Disentanglement Lock Go problems Folding Stick Tiling Tour Sliding Chess Maze (Logic maze) Word and Number Crossword Sudoku Puzzle video games Mazes Metapuzzles
Topics Brain teaser Dilemma Joke Optical illusion Packing problems Paradox Problem solving Puzzlehunt Syllogism
Lists Impossible puzzles Maze video games Nikoli puzzle types Puzzle video games Puzzle topics
v t e

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or 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 completely cover every region of the container, where objects are allowed to overlap.

In a bin packing problem, people are given:

• A container, usually a two- or three-dimensional convex region, possibly of infinite size. Multiple containers may be given depending on the problem.
• A set of objects, some or all of which must be packed into one or more 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 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 packing density. More commonly, the aim is to pack all the objects into as few containers as possible.^[1] In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.