Bin Packing Algorithm: First Fit and Best Fit Heuristics Detailed Guide

Bin Packing Problem Overview

The problem can be formally stated as follows: given a set of n items each with a size, pack them into as few bins as possible, where each bin has a fixed capacity. This is an NP-hard problem, meaning an exact solution for large inputs is computationally expensive, so heuristic algorithms are often applied to find good approximate solutions efficiently.

First Fit Heuristic Explained

The First Fit algorithm packs items sequentially into the first bin that has enough remaining space to accommodate the item. If no existing bin can accommodate the item, a new bin is opened.

First Fit Example

Consider items with sizes: 4, 8, 1, 4, 2, 1 and bins with capacity 10.

• Item 4 goes to Bin 1 (empty).
• Item 8 cannot fit in Bin 1 (remaining 6), so Bin 2 is opened.
• Item 1 fits in Bin 1 (remaining capacity 6 – 4 = 6).
• Item 4 fits in Bin 1 (remaining capacity 5 after adding item 1).
• Item 2 fits in Bin 2 (remaining capacity 2 after item 8).
• Item 1 fits in Bin 2 (remaining capacity 0 after item 2).

Best Fit Heuristic Explained

Best Fit places each item into the bin that will have the least remaining space after the item is placed but still can accommodate it. If there is no bin with enough space, a new bin is opened. This tends to fill bins more tightly than First Fit but requires scanning all bins.

Best Fit Example

Using the same items 4, 8, 1, 4, 2, 1 and bin capacity 10:

• Item 4 goes to Bin 1.
• Item 8 goes to Bin 2 (Bin 1 remaining 6 not enough for 8).
• Item 1 fits in Bin 1 (remaining 6 → 5).
• Item 4 fits in Bin 1 (remaining 5 → 1).
• Item 2 fits in Bin 2 (remaining 2 → 0).
• Item 1 fits in Bin 1 (remaining 1 → 0).

Comparison: First Fit vs Best Fit

While both heuristics are simple and run in reasonable time, they perform differently on various input sets:

Interactive Visual Example (Concept)

Below is HTML and JavaScript to simulate First Fit bin packing interactively. Users can input item sizes and see how items are placed live.

<label>Enter items separated by commas:</label>
<input type="text" id="itemInput" value="4,8,1,4,2,1" />
<button onclick="runFirstFit()">Run First Fit</button>
<div id="bins" style="margin-top:20px;"></div>

<script>
function runFirstFit() {
  const capacity = 10;
  const bins = [];
  const input = document.getElementById('itemInput').value;
  const items = input.split(',').map(x => parseInt(x.trim())).filter(x => !isNaN(x));
  bins.length = 0;
  for (const item of items) {
    let placed = false;
    for (const bin of bins) {
      const used = bin.reduce((a,b) => a+b, 0);
      if (used + item <= capacity) {
        bin.push(item);
        placed = true;
        break;
      }
    }
    if (!placed) bins.push([item]);
  }
  const binsDiv = document.getElementById('bins');
  binsDiv.innerHTML = '';
  bins.forEach((bin, i) => {
    binsDiv.innerHTML += `<div>Bin ${i+1}: [${bin.join(', ')}]</div>`;
  });
}
</script>

Summary

The Bin Packing Problem remains challenging due to its NP-hard nature. Heuristic algorithms like First Fit and Best Fit heuristics offer effective, efficient ways to get near-optimal solutions quickly. First Fit focuses on simplicity and speed by placing items in the first available bin, whereas Best Fit aims for tighter packing by considering bin fullness. Depending on the application, either heuristic can be chosen balancing simplicity against packing efficiency.

Understanding these heuristics lays the foundation for exploring more sophisticated algorithms like First Fit Decreasing, Best Fit Decreasing, or approximation algorithms to improve packing quality further.