Optimal Packing - Bin Packing with Greedy First-Fit Decreasing

Question

## Problem

You have `n` items with weights `w[i]` and bins of capacity `C`. Pack all items into the fewest bins possible.

Implement the First-Fit Decreasing (FFD) heuristic: sort items by weight descending, then for each item assign it to the first bin that has enough remaining capacity; if none, open a new bin.

Return the number of bins used and the assignment `bin_assignments[i]` (0-indexed bin for item `i`).

```python
def ffd_packing(
    weights: list[int],
    capacity: int
) -> tuple[int, list[int]]:
```

## Example

```
weights = [4, 7, 3, 6, 2], capacity = 10
Sorted desc: [(7,1),(6,3),(4,0),(3,2),(2,4)]
Bin 0: 7+3=10; Bin 1: 6+4=10; Bin 2: 2
Output: (3, [1, 0, 0, 1, 2])
```

## Follow-ups

1. Bin packing is NP-hard. What is the approximation ratio guarantee of FFD?
2. How does First-Fit (without sorting) compare to FFD in practice?
3. How would you adapt this for 2D packing (items have both width and height)?
4. If bins have different capacities, how does the algorithm change?

Optimal Packing - Bin Packing with Greedy First-Fit Decreasing

Question Details

Full Details

Topics

More from Amazon