Make the frequent cases fast and the rare case correct

Bin Packing Problem – combinatorial NP-hard problem

The bin packing problem asks for the minimum number k of identical bins of capacity C needed to store a finite collection of weights w1, w2, w3, … , wn so that no bin has weights stored in it whose sum exceeds the bin’s capacity. – Bin Packing (AMS).

for bins of size 10. No of bins required to store weights of size 3, 6, 2, 1, 5, 7, 2, 4, 1, 9?

When the number of bins is restricted to 1 and each item is characterized by both a volume and a value, the problem of maximizing the value of items that can fit in the bin is known as the knapsack problem

Next-Fit Algorithm:

Open a bin and place the items as they appear in the List. If an item on the list will not fit into the open bin, we close this bin permanently and open a new one and continue packing the remaining items in the list.

I have taken the images from the American Mathematical Society Article:

First-Fit Algorithm:

For First Fit the next item in the list into the first bin which has not been completely filled (thought of as numbered from left to right) into which it will fit. When bins are filled completely they are closed and if an item will not fit into any currently open bin, a new bin is opened


import java.util.*;
public class BinPacking
        public static void main(String[] args)
                System.out.println("Enter the number of items");
                Scanner input = new Scanner(;
                int items=input.nextInt();
                System.out.println("Enter the Size of the bin. All bins are of same size");
                int size = input.nextInt();
                System.out.println("Enter the items");
                ArrayList< Integer> bin = new ArrayList< Integer>();
                for(int member = 0; member < items ; member++)



                int count = 0;
                int binsize = items-1;
                int i = 0;
                while(i <= binsize)
                        int tmpsize = size;
                        tmpsize = tmpsize - bin.get(binsize--);
                        if(tmpsize >= bin.get(i))
                System.out.println("The Minimum number of bins required is " +count);

> java BinPacking
Enter the number of items
Enter the Size of the bin. All bins are of same size
Enter the items
The Minimum number of bins required is 5

In MathWorld they indicate In 1973, J. Ullman proved that this algorithm can differ from an optimal packing by as much at 70% . An alternative strategy first orders the items from largest to smallest, then places them sequentially in the first bin in which they fit. In 1973, D. Johnson showed that this strategy is never suboptimal by more than 22%, and furthermore that no efficient bin-packing algorithm can be guaranteed to do better than 22%. – MathWorld

Below Solution shows the most optimal solution: 4 bins are actually needed !

1 . American Mathematical Society
2 . Wolfram MathWorld

2 responses to “Bin Packing Problem – combinatorial NP-hard problem

  1. pazfernando May 15, 2012 at 5:29 pm

    Hi, I’m working on research about open source algorithms for packing problems pls I need to know about the license of your code for include in references
    Thanks in advance for you response and time

  2. EK May 25, 2012 at 6:55 pm

    You have those reversed – please revisit wiki as well as other documentation.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: