Bin Packing Problem Generator

What this generator does

Generates item sizes against either a fixed bin capacity or a choice of bin sizes at stated prices. With one size it packs by first-fit-decreasing and bounds the answer by the total size divided by the capacity. With several it packs, then drops each bin to the cheapest type that still holds what ended up inside it, and bounds the cost by the total size charged at the best value per unit of capacity. Either way it reports whether the answer matches the bound.

How to use this tool

1. Choose how many items to pack, and whether the bins are all one size or come in several at different prices.
2. Try to fit them into as few bins as the capacity allows.
3. Reveal the packing to compare against first-fit-decreasing.
4. Check whether the bound proves that packing optimal or leaves a gap.

Understanding the controls

How many items

Between 4 and 14, or up to 16 when the bins vary. Larger instances would not change the method, but they make the packing tedious to check by hand.

What the bins are like

All one size, where the question is how few bins will do; or several sizes at different prices, where the question is how little you can spend. No pointless bin type is ever offered — one that is smaller and dearer than another would never be bought.

Seed

Reproduces the same sizes and capacity, so an instance can be set as an exercise and marked later.

Show the answer

Reveals the packing bin by bin, with the load in each, and states whether the lower bound proves it optimal.

Common use cases

• Practice instances for a packing or scheduling exercise
• Demonstrating what a lower bound proves and what it does not
• Testing a packing heuristic against a known feasible answer
• Teaching the difference between a good answer and a proved answer
• Setting the variable-sized version, where the cheapest answer is not the one using fewest bins
• Producing the same instance twice for a class comparison

How this generator works

First-fit-decreasing sorts the items largest first and drops each into the first bin with room. That is a well-understood heuristic with a known worst case. The lower bound is arithmetic: total size divided by capacity, rounded up, since no packing can do better than filling every bin completely. When the bins vary, a new bin is opened as the best value that fits, and a second pass then drops every bin to the cheapest type still large enough for its contents — the bin opened for one big item is often far too big once nothing else joins it. The cost bound is the same idea as the bin bound: no bin is ever better value than the best-value type, and capacity cannot be created, so the total size at that rate is a floor. All of it is checked before display — every item packed exactly once, no bin over its own capacity, the cost re-added from the bins, and no bin left dearer than it needed to be.

Randomness and fairness

The sizes and the capacity are random; the packing and the bound are computed from them. Seeded instances are reproducible and therefore explicitly not cryptographically secure, and unseeded ones use the browser's cryptographically secure generator.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• The packing is a heuristic answer, not a proved optimum, except where it happens to meet the bound.
• The bin sizes and prices are drawn for you; there is no way to type in the box sizes a particular supplier sells.
• Items are one-dimensional sizes, so this is not rectangle or pallet packing.
• No search is run for a better packing, so a stated gap is not evidence that a better packing exists.
• Instances are not stored between visits.

Privacy and your data

Sizes, packings and bounds are computed in your browser. No instance or seed is transmitted or retained.