Skip to content
Atlas, your robot learning host

Interim portrait

Atlas · Foundations bin-packing

Hello, little human. I am Atlas. One useful idea is plenty for a beginning. Read the explanation, then explore an example.

Choose your robot No recording yet · text complete
concept for junior engineers
  • devops

BIN Packing

Bin packing places every whole item in a fixed-capacity bin while seeking the fewest bins; a legal placement need not be an optimal one.

Tune in, human.

Reviewed videos and Shorts

Captions requested · no autoplay

Finding reviewed videos…

    Keep the useful bits, human.

    Beginner field notes

    Choose explanation level
    • This bin-packing model places every whole item in one fixed-capacity bin and seeks the fewest bins. It does not choose a valuable subset and leave the rest out.
    • A bin is allowed only when the sum of its assigned item sizes does not exceed capacity. Unused room elsewhere does not excuse an overloaded bin.
    • Finding a legal arrangement shows that many bins suffice. It does not prove no arrangement with fewer bins exists.
    See a worked example

    Compare a heuristic construction with an instance-specific optimum proof

    Sample only. Nothing here runs on your computer.

    Example input · do not paste
    OFFLINE Lantern Archive paper placement; no boxes, machines or files are actually changed.
Four distinct, whole items: A size 4, B size 4, C size 6, D size 6. Each item must be assigned exactly once and cannot be split. Sizes are positive integer units of one additive resource; every bin has capacity 10. A bin is legal when its total is at most 10, so equality is allowed. Ignore shape, overhead, timing, CPU/memory combinations, affinity and every other constraint.
Start with no bins. Give each newly opened bin the next label P1,P2,P3. Once an item is assigned, do not move or remove it. There are enough identical bins; each item fits an empty bin.
First-fit rule: take items in the stated order. Check already opened bins in their opening order; put the item in the first whose remaining capacity is at least its size. If none fits, open a new bin and put it there.
Run two separate paper constructions from no bins, with identical data and constraints:
1. First-fit input order A4, B4, C6, D6.
2. First-fit decreasing: sort by decreasing size, keeping original order for equal sizes, then apply first-fit.
Show every assignment and final bin load. Use total size divided by capacity, rounded upward, as a necessary lower bound; decide whether a shown placement attains it. The comparison does not execute code or an optimizer.
    Example output · do not paste
    INPUT-ORDER FIRST-FIT
A→P1: load 4, remaining 6. B→P1: load 8, remaining 2.
C cannot fit P1, so C→P2: load 6, remaining 4.
D cannot fit P1 or P2, so D→P3: load 6, remaining 4.
Final: P1[A,B]=8; P2[C]=6; P3[D]=6. Bins used 3; remaining capacities[2, 4, 4].
STABLE FIRST-FIT DECREASING
Order C6, D6, A4, B4. C→P1: load 6, remaining 4.
D cannot fit P1, so D→P2: load 6, remaining 4.
A fits the first bin P1 exactly: P1[C,A]=10, remaining 0.
B cannot fit P1, but fits P2 exactly: P2[D,B]=10, remaining 0.
Final bins used 2; loads[10, 10]; remaining capacities[0, 0].
PROOF FOR THIS INSTANCE
Total size=4+4+6+6=20. At least ceil(20/10)=2 bins are required. The shown legal two-bin placement reaches the bound, so the optimum for this input is 2. First-fit’s 3 is feasible but not optimal here. This does not certify the heuristic on other inputs.

    Separate the input-order construction, sorted-order construction and proof. Stable tie handling determines identities, first-fit determines the earliest fitting bin, and the bound uses only total size and common capacity. Equality at 10 is legal. Reaching a valid lower bound proves this particular solution optimal; merely computing that bound or naming a heuristic does not.

    Visual

    On the same fixed input, first-fit opens three bins and stable first-fit decreasing opens two. The total-size lower bound is two and the latter placement reaches it, certifying this example only. No claim is made that decreasing order is always optimal.

    The reviewed description and complete diagram source are available here.

    Read the complete diagram source

    This is the source for the reviewed diagram, not a command to run.

    flowchart TD
  I["Same whole items: A4, B4, C6, D6; capacity 10"] --> F["First-fit input order A,B,C,D"]
  I --> S["Stable decreasing order C,D,A,B"]
  F --> T["3 bins: AB load 8; C load 6; D load 6"]
  S --> U["2 bins: CA load 10; DB load 10"]
  I --> L["Total 20 / capacity 10 gives lower bound 2"]
  U --> O["This instance reaches lower bound: optimum 2"]
  L --> O
    Sources and full explanation

    Notes sources · Beginner

    AI source review · 2026-10-17

    Reviewed explanation

    Bin packing turns one kind of resource placement into an explicit constrained optimization problem. In the one-dimensional form used here, each item has a known size, all bins share a capacity, and every item must be placed whole in exactly one bin. The constraint keeps every load within capacity. The objective is to use the fewest bins that hold all the items, rather than choose a valuable subset and leave the rest out.

    A simple construction rule is first-fit. Take the next item in the input order and inspect existing bins in the order they opened; choose the first where it fits. Open another only if none fits. With capacity 10 and items A4, B4, C6, D6, A and B share the first bin at load 8. C cannot fit there and opens a second at 6. D fits neither existing bin and opens a third. This is feasible, but feasibility does not establish optimality.

    First-fit decreasing changes the processing order before applying that same placement rule. It needs the full known item list and sorts by non-increasing size. To preserve identity in this example, equal sizes keep their original relative order: C6, D6, A4, B4. C and D initially open separate bins. A then fits exactly alongside C, and B alongside D, so the result uses two bins of load 10 each. Nothing is repacked after assignment.

    We can prove the minimum for this small instance without running a solver. The four sizes sum to 20. Because one bin holds at most 10, fewer than two bins cannot hold that total. This is a lower bound. The displayed two-bin construction meets it, so two is optimal for these exact items and assumptions. By contrast, the first-fit construction only shows that three bins suffice. It is not the minimum here.

    The volume bound is a necessary condition, not a general construction recipe. Indivisible item sizes may prevent filling bins as tightly as their total suggests. A heuristic is a rule for finding a candidate arrangement; this lesson gives no promise that first-fit decreasing always returns an optimum or always improves another order. A different input needs its own analysis or an appropriate exact optimization method and result check.

    Actual resource placement can require several capacities at once, compatibility restrictions, overhead, timing or movement costs. Those are additional constraints or objectives, and cannot be inferred from this one-number-per-item model. The example keeps the advanced resource-placement objective while isolating one explainable mathematical case. It makes no claim about an actual memory/CPU scheduler, deployed machines, performance, price or a solver run.

    • NIST Dictionary of Algorithms and Data Structures: bin packing problem

      Defines constrained packing and the common fewest-fixed-capacity-bins objective, while distinguishing variants such as dimensions and resource measures. It does not equate this one-dimensional example with a real scheduler.

    • Google OR-Tools: The Bin Packing Problem

      The official model assigns each item to exactly one bin, limits its additive load to the common capacity and minimizes bins used. The lesson borrows these mathematical constraints, not solver code, runtime results or an operational deployment procedure.

    • Mathematical Optimization book: Bin packing and cutting stock problems

      The method authors describe non-increasing-size preprocessing followed by the first open bin that fits, opening another only when needed. They explicitly distinguish a heuristic from guaranteed optimization. The chapter also illustrates an instance-specific total-capacity lower bound. Only these explanations are used; its code/solver setup is not executed.

    AI source comparison recorded 2026-10-17. Human learner validation is pending.

    Quick quiz · one question

    Compare feasible constructions with a lower bound

    Sample scenario. Offline, one-dimensional, unsplittable positive integer items A size 4, B size 4, C size 6, D size 6 and capacity 10. All items fit alone; no other constraints or moves. First-fit scans open containers in opening order. Decreasing order is stable on equal sizes. This is a bounded paper construction, not a solver or a general heuristic-optimality guarantee.

    Paper capacity
    Each container holds at most 10 integer units of one additive resource. Items are whole and each fits alone. No splitting, moving, removal, hidden repacking, real allocation or other constraint.
    Distinct items
    A: size 4; B: size 4; C: size 6; D: size 6
    Trial first-fit
    Use the original item order. Scan already opened containers in opening order; choose the first that fits, otherwise open the next one. Never revise an earlier placement.
    Trial decreasing
    First sort by decreasing size, preserving original order for equal sizes. Then scan open containers in opening order for the first fit. This is a heuristic, not a universal optimality promise.

    Run input-order first-fit and stable first-fit decreasing separately. Which placements result, and what does the total-size lower bound establish for this one input?

    Answers stay on this device.

    Sources and exercise scope
    • NIST Dictionary of Algorithms and Data Structures: bin packing problem

      Defines constrained packing and the common fewest-fixed-capacity-bins objective, while distinguishing variants such as dimensions and resource measures. It does not equate this one-dimensional example with a real scheduler.

    • Mathematical Optimization book: Bin packing and cutting stock problems

      The method authors describe non-increasing-size preprocessing followed by the first open bin that fits, opening another only when needed. They explicitly distinguish a heuristic from guaranteed optimization. The chapter also illustrates an instance-specific total-capacity lower bound. Only these explanations are used; its code/solver setup is not executed.

    Original synthetic exercise. AI comparison against the reviewed lesson recorded on 2026-10-17; the references above state their scope. Human learner validation has not been run. A result here records this attempt; it does not establish mastery.

    Save or adjust this lesson
    Reference notes · file removal and public access

    Robot reference desk

    Understand what can change

    These reviewed public notes are available to everyone. They do not establish that an operation ran or inspect your files, backups or permissions.

    File removal

    Before deleting files: deleting a file can remove it without putting it in Trash or a recycle bin, and recovery is not guaranteed. Check the intended targets and whether a usable backup or recovery option exists before continuing.

    Sources for this note

    Public access

    Before making a resource public: public read access can let anyone view the exposed content, and public write access can allow changes to data. Check the actual audience, exposed content and allowed operations before continuing. This guidance does not inspect or change your permissions.

    Sources for this note

    A link can carry these public reference topics in its fragment. Page scripts, extensions, browser history and copied links can read them. This page attempts to minimize that fragment when JavaScript runs; reloading afterward can lose the selection. No project details or conversation text belong in a lesson link. Privacy details.