The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.9 Bin Packing

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A set of n items with sizes d_1,...,d_n. A set of m bins with capacity c_1,...,c_m.

Problem: How do you store the set of items using the fewest number of bins?

Excerpt from The Algorithm Design Manual: Bin packing arises in a variety of packaging and manufacturing problems. Suppose that you are manufacturing widgets with parts cut from sheet metal, or pants with parts cut from cloth. To minimize cost and waste, we seek to lay out the parts so as to use as few fixed-size metal sheets or bolts of cloth as possible. Identifying which part goes on which sheet in which location is a bin-packing variant called the cutting stock problem. After our widgets have been successfully manufactured, we will be faced with another bin packing problem, namely how best to fit the boxes into trucks to minimize the number of trucks needed to ship everything.

Implementations

  • Silvano Martello and Paolo Toth's Knapsack Problem (FORTRAN) (rating 9)
  • David Pisinger's optimization codes (C) (rating 8)
  • Program - A Practical Approach for Computing the Diameter of a Point-Set (C) (rating 7)
  • Xtango and Polka Algorithm Animation Systems (C++,C) (rating 2)

    • Recommended Books

    Sphere packings, lattices, and groups by J. Conway and N. Sloane Knapsack Problems : Algorithms and Computer Implementations by Silvano Martello and Paolo Toth Computer Algorithms by S. Baase

    Related Problems
    Knapsack Problem
    Job Scheduling
    Set Packing


    This page last modified on 2008-07-10 .
    www.algorist.com