Inventory Packer

You're given a list of items, each with a weight and a size. The warehouse hands out bins with two caps, a weight limit and a size limit. Assign every item to a bin such that no bin exceeds either limit. The output is a map from item name to the bin id that holds it. The goal is to minimize the number of bins.

The rules impose a few constraints worth tracing through. Items can't be split across bins, and both caps apply at the same time, so a bin holding the Monitor and Keyboard above is full on weight even though it still has a sliver of size room left for the Mouse. The warehouse hands you one method to list the bins you've already opened in creation order and another method to open a fresh bin that returns its new id.

The problem is a classic bin-packing problem. Finding the absolute minimum number of bins is NP-hard, which means there's no known polynomial algorithm that always produces the optimum. What we can do is pick a fast heuristic, a strategy that usually produces a near-optimal answer even though it gives up the guaranteed optimum, that produces a near-optimal count on the inputs we care about.

The simplest workable heuristic is First-Fit. For each item in the order you receive it, walk the existing bins and put the item in the first one that still has room for it. If nothing fits, open a brand-new bin for the item and move on to the next one.