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
- Bin Packing: 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
}
}
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);
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();
}