In this post I will present example 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
- First Fit Decreasing Algorithm
- Download Source Code for 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);

}

return;

}

// iterate over bins

Integer currentItem = in.get(currentPosition);

for (Bin bin : bins) {

if (bin.put(currentItem)) {

bruteforce(in, currentPosition + 1);

bin.remove(currentItem);

} // else: item did not fit in bin, ignore

}

}

## First Fit Decreasing Algorithm

Implementing the first fit decreasing algorithm is quite simple. Just sort your input (descending), and then iterate over your input, packing each item into the first bin it fits into.

* first fit decreasing solution 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);

newBin.put(currentItem);

bins.add(newBin);

putItem = true;

} else if (bins.get(currentBin).put(currentItem)) {

// item fit in bin

putItem = true;

} else {

// try next bin

currentBin++;

}

}

}

return bins.size();

}