One-dimensional bin packing is a classic problem with many practical applications related to minimization of space or time. It is a hard problem for which many different heuristic solutions have been proposed. The goal is to pack a collection of objects into the minimum number of fixed-size "bins".
The bpack.icn
program illustrates the behavior of six different packing algorithms.
It is a streamlined version of the older binpack
program
from the Icon program library.
Two shelves of objects appear in the program display. The top shelf shows the candidate objects to be packed. The bottom shelf shows the results of packing. Objects larger than half a bin are colored orange; smaller objects are blue.
The File
menu offers three choices:
About
summarizes the available packing algorithms
New
creates a new, random set of objects for packing
Quit
exits the program
The Reorder
menu rearranges the candidate objects on the top shelf.
The Pack
menu selects an algorithm and packs the
objects onto the bottom shelf using the selected algorithm.
These operations are illustrated in the following sections.
Reorder
MenuReorder
menu rearrange the top shelf of
candidate objects in various ways.
Pack
Menu
The entries in the Pack
menu take the objects from the top
shelf and pack them into the bottom shelf using different algorithms.
The resulting display notes the packing algorithm used by its initials,
and also indicates the number of bins required.
All algorithms take the objects from the top shelf in order and place them one at a time. A new bin is created whenever the algorithm cannot use an existing bin.
Best Fit
algorithm.
E.G. Coffman, Jr., M.R. Garey, and D.S. Johnson. Approximation Algorithms for Bin-Packing -- An Updated Survey. In Algorithm Design for Computer System Design, ed. by Ausiello, Lucertini, and Serafini. Springer-Verlag, 1984.
David S. Johnson. Fast Algorithms for Bin Packing. Journal of Computer and System Sciences 8, 272-314 (1974).