Bin Packing, What is It?

   Bin Packing is a mathematical way to deal with efficiently fitting Elements into Bins.  Now, a Bin is something that can hold inside itself a certain amount (it's Bin Height).  Every Element is of a certain, non-zero, and positive value ( Element Height).  The goal of every Bin Packing algorithm is to use the least amount of Bins to hold the required number of Elements.

Bin:  A fixed-size container that can hold Elements.
Bin Height:  The specified amount that each Bin can hold.
Element:  An item that is to be placed in a Bin having a certain Element Height.
Element Height:  The amount of Bin space the Element will take up if placed in that Bin.

   Now, why is this useful?  Several real-world problems can be optimized and made to run more efficient by employing this solution.  Image for a moment that you have a package of blank CDs that can hold 80 minutes of music each.  You have 100 songs of varying lengths.  You want to use the least amount of blank CDs to fit all of your songs on.  This is a Bin Packing problem.

Bin: The blank CDs.
Bin Height:  80 (minutes) or 4,800 (seconds).
Element:  One song.
Element Height:  The length of each song in minutes or seconds.

   Other examples include:  Using the least amount of boards to cut out small pieces for a construction project, fitting large files onto small capacity hard drives, etc.

   There is one hitch with a Bin Packing problem, that is a Bin Packing problem is classified as NP-Complete.  This basically means that their is no way of  being guaranteed the best solution without checking every possible solution.  This is not to say that a solution reached by one of the following algorithms is not optimal, it may be.  The classic NP-Complete problem is the Traveling Salesman Problem.  The algorithms presented here do give reasonable, practical solutions however.