Bin Packing Algorithm (Java)

In this post I will present example Java code for solving the Bin Packing Problem. I will not go into what exactly Bin Packing is, as there are enough websites that do a good job describing it. As always, wikipedia is a good start to get a general overview: Wikipedia Bin Packing Problem.

Bin Packing: Brute Force Solution

To check all possible solutions for the bin packaging problem (brute force), a recursive approach can be used: Iterate over all bins, try to put the current item in the bin and – if it fits – call the same method with the next item.

     * bruteforce solution to bin packing problem.
     * @param in list of items to be packed
     * @param currentPosition position in input list

    private void bruteforce(List<Integer> in, int currentPosition) {
        if (currentPosition >= in.size()) { // reached last item, done with this iteration
            int filledBins = getFilledBinsCount();
            if (filledBins < currentBestSolution) { // is this solution better than the current best?
                currentBestSolution = filledBins; // then save it
                currentBestBins = deepCopy(bins);
        // iterate over bins
        Integer currentItem = in.get(currentPosition);
        for (Bin bin : bins) {
            if (bin.put(currentItem)) {
                bruteforce(in, currentPosition + 1);
            } // else: item did not fit in bin, ignore

Bin Packing: First Fit Decreasing Algorithm

The Bin Packing Problem can also be solved by an algorithm, called first fit decreasing. Implementing the first fit decreasing algorithm is quite simple. Just sort your input (descending), and then iterate over it, packing each item into the first bin it fits into.

     * first fit decreasing algorithm for bin packing problem

    public int firstFitDecreasing() {
        Collections.sort(in, Collections.reverseOrder()); // sort input by size (big to small)
        bins.add(new Bin(binSize)); // add first bin
        for (Integer currentItem : in) {
            // iterate over bins and try to put the item into the first one it fits into
            boolean putItem = false; // did we put the item in a bin?
            int currentBin = 0;
            while (!putItem) {
                if (currentBin == bins.size()) {
                    // item did not fit in last bin. put it in a new bin
                    Bin newBin = new Bin(binSize);
                    putItem = true;
                } else if (bins.get(currentBin).put(currentItem)) {
                    // item fit in bin
                    putItem = true;
                } else {
                    // try next bin
        return bins.size();

Download Source Code for Bin Packing Problem

Java Bin Packing Source Code [3.9 kB]

Related Posts:

Leave a Reply

Your email address will not be published.