<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P094-packing-planner/ | updated: 2026-10-15 -->

# P094 Packing planner

Items into bins by First Fit, Best Fit and First Fit Decreasing, against the fewest bins found by search; and the 0/1 knapsack - the most value that fits, by dynamic programming over every weight - against greedy best value per kilogram.

EML-P project `projects/packing-planner` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/packing-planner` runs it and `eml project verify projects/packing-planner` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: bin-packing-first-fit (https://efficientnewlanguage.org/cases/095-bin-packing-first-fit/), subset-sum-backtracking (https://efficientnewlanguage.org/cases/123-subset-sum-backtracking/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
3
0
3
10
11 2
3
10
1 1 1 1 1 1 1 1 1 1 1 1 1
3
10
a b
3

4
50
10 60 20
4
101
4
50
0 5
4

5
```

Screen:

```text
== Packing planner ==
Bins: three quick rules against the fewest possible. A knapsack: the most value that fits.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 0
Pick a number from 1 to 5.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> x
Pick a number from 1 to 5.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 0
The capacity is a whole number from 1 to 100.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 10
item sizes (1 to 12 of them, each 1 to the capacity)> 11 2
Type 1 to 12 whole numbers, each from 1 to the capacity.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 10
item sizes (1 to 12 of them, each 1 to the capacity)> 1 1 1 1 1 1 1 1 1 1 1 1 1
Type 1 to 12 whole numbers, each from 1 to the capacity.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 10
item sizes (1 to 12 of them, each 1 to the capacity)> a b
Type 1 to 12 whole numbers, each from 1 to the capacity.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 
Cancelled.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 4
knapsack capacity in kg (1 to 100)> 50
items as weight value pairs (like 10 60 20 100)> 10 60 20
Type 1 to 12 pairs of whole numbers from 1 to 999: a weight, then its value.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 4
knapsack capacity in kg (1 to 100)> 101
The capacity is a whole number from 1 to 100.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 4
knapsack capacity in kg (1 to 100)> 50
items as weight value pairs (like 10 60 20 100)> 0 5
Type 1 to 12 pairs of whole numbers from 1 to 999: a weight, then its value.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 4
knapsack capacity in kg (1 to 100)> 
Cancelled.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 5
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
2
3
13
8 4 2 6 3 3
1
4
10
5 10 4 40 6 30 3 50
2
3
10
6 6 5 5 4 4 3 3 2 2
1
5
```

Screen:

```text
== Packing planner ==
Bins: three quick rules against the fewest possible. A knapsack: the most value that fits.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 1
7 items, 30 in all, bins of 10:
  First Fit            4 bins  [5+4+1]  [7+2]  [8]  [3]
  Best Fit             4 bins  [5+4+1]  [7+2]  [8]  [3]
  First Fit Decreasing 3 bins  [8+2]  [7+3]  [5+4+1]
  fewest possible      3 bins  [8+2]  [7+3]  [5+4+1]
First Fit opens bins early for items that later ones would have fitted around; taking the largest first usually avoids it, but not always.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 2
  item  weight  value
  #1     10 kg    60
  #2     20 kg    100
  #3     30 kg    120
Most value within 50 kg: 220, from #2 (20 kg, 100), #3 (30 kg, 120).
Best value per kg first: 160, from #1 (10 kg, 60), #2 (20 kg, 100).
The greedy rule fills up on the best ratios and leaves room it cannot use; the table over every weight finds the better mix.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 13
item sizes (1 to 12 of them, each 1 to the capacity)> 8 4 2 6 3 3
6 items for bins of 13.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 1
6 items, 26 in all, bins of 13:
  First Fit            3 bins  [8+4]  [2+6+3]  [3]
  Best Fit             3 bins  [8+4]  [2+6+3]  [3]
  First Fit Decreasing 3 bins  [8+4]  [6+3+3]  [2]
  fewest possible      2 bins  [8+3+2]  [6+4+3]
First Fit opens bins early for items that later ones would have fitted around; taking the largest first usually avoids it, but not always.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 4
knapsack capacity in kg (1 to 100)> 10
items as weight value pairs (like 10 60 20 100)> 5 10 4 40 6 30 3 50
4 items for a knapsack of 10 kg.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 2
  item  weight  value
  #1     5 kg    10
  #2     4 kg    40
  #3     6 kg    30
  #4     3 kg    50
Most value within 10 kg: 90, from #2 (4 kg, 40), #4 (3 kg, 50).
Best value per kg first: 90, from #4 (3 kg, 50), #2 (4 kg, 40).
Here the greedy rule finds the best too.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 3
bin capacity (1 to 100)> 10
item sizes (1 to 12 of them, each 1 to the capacity)> 6 6 5 5 4 4 3 3 2 2
10 items for bins of 10.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 1
10 items, 40 in all, bins of 10:
  First Fit            4 bins  [6+4]  [6+4]  [5+5]  [3+3+2+2]
  Best Fit             4 bins  [6+4]  [6+4]  [5+5]  [3+3+2+2]
  First Fit Decreasing 4 bins  [6+4]  [6+4]  [5+5]  [3+3+2+2]
  fewest possible      4 bins  [6+4]  [6+4]  [5+5]  [3+3+2+2]
First Fit already does as well as can be done here.

1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit
choice> 5
Bye.
```

## Modules

### main.eml

```eml
# P094 packing planner: items into bins by First Fit, Best Fit and First
# Fit Decreasing, against the fewest bins possible; and the 0/1 knapsack by
# dynamic programming, against the greedy best-value-per-weight rule.
import packing

def plain(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def numbers(s):
    [] => out
    "" => w
    for c in s + " ":
        if c == " " or c == ",":
            if w != "":
                if len(w) > 3:
                    return []
                0 => n
                for d in w:
                    if not (d >= "0" and d <= "9"):
                        return []
                    n * 10 + int(d) => n
                out + [n] => out
            "" => w
        else:
            w + c => w
    return out

def bins_text(sizes, bins):
    "" => s
    for b in bins:
        "" => t
        0 => used
        for i in b:
            if t != "":
                t + "+" => t
            t + str(sizes[i]) => t
            used + sizes[i] => used
        if s != "":
            s + "  " => s
        s + "[" + t + "]" => s
    return s

def count(n):
    if n == 1:
        return "1 bin "
    return str(n) + " bins"

def pack(sizes, cap):
    packing.first_fit(sizes, cap, packing.in_order(len(sizes))) => ff
    packing.best_fit(sizes, cap) => bf
    packing.first_fit(sizes, cap, packing.largest_first(sizes)) => ffd
    packing.fewest(sizes, cap) => best
    0 => total
    for s in sizes:
        total + s => total
    (str(len(sizes)) + " items, " + str(total) + " in all, bins of " + str(cap) + ":") ^0
    ("  First Fit            " + count(len(ff)) + "  " + bins_text(sizes, ff)) ^0
    ("  Best Fit             " + count(len(bf)) + "  " + bins_text(sizes, bf)) ^0
    ("  First Fit Decreasing " + count(len(ffd)) + "  " + bins_text(sizes, ffd)) ^0
    ("  fewest possible      " + count(len(best)) + "  " + bins_text(sizes, best)) ^0
    if len(ff) > len(best):
        "First Fit opens bins early for items that later ones would have fitted around; taking the largest first usually avoids it, but not always." ^0
    else:
        "First Fit already does as well as can be done here." ^0

def items_text(items, chosen):
    "" => s
    for i in chosen:
        if s != "":
            s + ", " => s
        s + "#" + str(i + 1) + " (" + str(items[i][0]) + " kg, " + str(items[i][1]) + ")" => s
    if s == "":
        "nothing" => s
    return s

def knap(items, cap):
    "  item  weight  value" ^0
    for i in [0:len(items) - 1]:
        ("  #" + str(i + 1) + "     " + str(items[i][0]) + " kg    " + str(items[i][1])) ^0
    packing.knapsack(items, cap) => best
    packing.by_value(items, cap) => greedy
    ("Most value within " + str(cap) + " kg: " + str(best[0]) + ", from " + items_text(items, best[1]) + ".") ^0
    ("Best value per kg first: " + str(greedy[0]) + ", from " + items_text(items, greedy[1]) + ".") ^0
    if greedy[0] < best[0]:
        "The greedy rule fills up on the best ratios and leaves room it cannot use; the table over every weight finds the better mix." ^0
    else:
        "Here the greedy rule finds the best too." ^0

def new_sizes(sizes, cap):
    plain(input("bin capacity (1 to 100)> ")) => s
    if s == "":
        "Cancelled." ^0
        return [sizes, cap]
    numbers(s) => c
    if len(c) != 1 or c[0] < 1 or c[0] > 100:
        "The capacity is a whole number from 1 to 100." ^0
        return [sizes, cap]
    plain(input("item sizes (1 to 12 of them, each 1 to the capacity)> ")) => t
    numbers(t) => xs
    True => ok
    for x in xs:
        if x < 1 or x > c[0]:
            False => ok
    if not ok or len(xs) < 1 or len(xs) > 12:
        "Type 1 to 12 whole numbers, each from 1 to the capacity." ^0
        return [sizes, cap]
    (str(len(xs)) + " items for bins of " + str(c[0]) + ".") ^0
    return [xs, c[0]]

def new_items(items, cap):
    plain(input("knapsack capacity in kg (1 to 100)> ")) => s
    if s == "":
        "Cancelled." ^0
        return [items, cap]
    numbers(s) => c
    if len(c) != 1 or c[0] < 1 or c[0] > 100:
        "The capacity is a whole number from 1 to 100." ^0
        return [items, cap]
    plain(input("items as weight value pairs (like 10 60 20 100)> ")) => t
    numbers(t) => xs
    True => ok
    for x in xs:
        if x < 1:
            False => ok
    if not ok or len(xs) < 2 or len(xs) > 24 or len(xs) % 2 != 0:
        "Type 1 to 12 pairs of whole numbers from 1 to 999: a weight, then its value." ^0
        return [items, cap]
    [] => out
    0 => i
    while i < len(xs):
        out + [[xs[i], xs[i + 1]]] => out
        i + 2 => i
    (str(len(out)) + " items for a knapsack of " + str(c[0]) + " kg.") ^0
    return [out, c[0]]

[5, 7, 4, 2, 8, 3, 1] => sizes
10 => cap
[[10, 60], [20, 100], [30, 120]] => items
50 => kcap

"== Packing planner ==" ^0
"Bins: three quick rules against the fewest possible. A knapsack: the most value that fits." ^0
True => running
while running:
    "" ^0
    "1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit" ^0
    plain(input("choice> ")) => choice
    if choice == "1":
        pack(sizes, cap)
    elif choice == "2":
        knap(items, kcap)
    elif choice == "3":
        new_sizes(sizes, cap) => r
        r[0] => sizes
        r[1] => cap
    elif choice == "4":
        new_items(items, kcap) => r
        r[0] => items
        r[1] => kcap
    elif choice == "5":
        False => running
    else:
        "Pick a number from 1 to 5." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import packing

def plain(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def numbers(s):
    out = []
    w = ""
    for c in s + " ":
        if c == " " or c == ",":
            if w != "":
                if len(w) > 3:
                    return []
                n = 0
                for d in w:
                    if not (d >= "0" and d <= "9"):
                        return []
                    n = n * 10 + int(d)
                out = out + [n]
            w = ""
        else:
            w = w + c
    return out

def bins_text(sizes, bins):
    s = ""
    for b in bins:
        t = ""
        used = 0
        for i in b:
            if t != "":
                t = t + "+"
            t = t + str(sizes[i])
            used = used + sizes[i]
        if s != "":
            s = s + "  "
        s = s + "[" + t + "]"
    return s

def count(n):
    if n == 1:
        return "1 bin "
    return str(n) + " bins"

def pack(sizes, cap):
    ff = packing.first_fit(sizes, cap, packing.in_order(len(sizes)))
    bf = packing.best_fit(sizes, cap)
    ffd = packing.first_fit(sizes, cap, packing.largest_first(sizes))
    best = packing.fewest(sizes, cap)
    total = 0
    for s in sizes:
        total = total + s
    print(str(len(sizes)) + " items, " + str(total) + " in all, bins of " + str(cap) + ":")
    print("  First Fit            " + count(len(ff)) + "  " + bins_text(sizes, ff))
    print("  Best Fit             " + count(len(bf)) + "  " + bins_text(sizes, bf))
    print("  First Fit Decreasing " + count(len(ffd)) + "  " + bins_text(sizes, ffd))
    print("  fewest possible      " + count(len(best)) + "  " + bins_text(sizes, best))
    if len(ff) > len(best):
        print("First Fit opens bins early for items that later ones would have fitted around; taking the largest first usually avoids it, but not always.")
    else:
        print("First Fit already does as well as can be done here.")

def items_text(items, chosen):
    s = ""
    for i in chosen:
        if s != "":
            s = s + ", "
        s = s + "#" + str(i + 1) + " (" + str(items[i][0]) + " kg, " + str(items[i][1]) + ")"
    if s == "":
        s = "nothing"
    return s

def knap(items, cap):
    print("  item  weight  value")
    for i in range(0, len(items)):
        print("  #" + str(i + 1) + "     " + str(items[i][0]) + " kg    " + str(items[i][1]))
    best = packing.knapsack(items, cap)
    greedy = packing.by_value(items, cap)
    print("Most value within " + str(cap) + " kg: " + str(best[0]) + ", from " + items_text(items, best[1]) + ".")
    print("Best value per kg first: " + str(greedy[0]) + ", from " + items_text(items, greedy[1]) + ".")
    if greedy[0] < best[0]:
        print("The greedy rule fills up on the best ratios and leaves room it cannot use; the table over every weight finds the better mix.")
    else:
        print("Here the greedy rule finds the best too.")

def new_sizes(sizes, cap):
    s = plain(input("bin capacity (1 to 100)> "))
    if s == "":
        print("Cancelled.")
        return [sizes, cap]
    c = numbers(s)
    if len(c) != 1 or c[0] < 1 or c[0] > 100:
        print("The capacity is a whole number from 1 to 100.")
        return [sizes, cap]
    t = plain(input("item sizes (1 to 12 of them, each 1 to the capacity)> "))
    xs = numbers(t)
    ok = True
    for x in xs:
        if x < 1 or x > c[0]:
            ok = False
    if not ok or len(xs) < 1 or len(xs) > 12:
        print("Type 1 to 12 whole numbers, each from 1 to the capacity.")
        return [sizes, cap]
    print(str(len(xs)) + " items for bins of " + str(c[0]) + ".")
    return [xs, c[0]]

def new_items(items, cap):
    s = plain(input("knapsack capacity in kg (1 to 100)> "))
    if s == "":
        print("Cancelled.")
        return [items, cap]
    c = numbers(s)
    if len(c) != 1 or c[0] < 1 or c[0] > 100:
        print("The capacity is a whole number from 1 to 100.")
        return [items, cap]
    t = plain(input("items as weight value pairs (like 10 60 20 100)> "))
    xs = numbers(t)
    ok = True
    for x in xs:
        if x < 1:
            ok = False
    if not ok or len(xs) < 2 or len(xs) > 24 or len(xs) % 2 != 0:
        print("Type 1 to 12 pairs of whole numbers from 1 to 999: a weight, then its value.")
        return [items, cap]
    out = []
    i = 0
    while i < len(xs):
        out = out + [[xs[i], xs[i + 1]]]
        i = i + 2
    print(str(len(out)) + " items for a knapsack of " + str(c[0]) + " kg.")
    return [out, c[0]]

sizes = [5, 7, 4, 2, 8, 3, 1]
cap = 10
items = [[10, 60], [20, 100], [30, 120]]
kcap = 50
print("== Packing planner ==")
print("Bins: three quick rules against the fewest possible. A knapsack: the most value that fits.")
running = True
while running:
    print("")
    print("1) pack the items  2) fill the knapsack  3) new items to pack  4) new knapsack items  5) quit")
    choice = plain(input("choice> "))
    if choice == "1":
        pack(sizes, cap)
    elif choice == "2":
        knap(items, kcap)
    elif choice == "3":
        r = new_sizes(sizes, cap)
        sizes = r[0]
        cap = r[1]
    elif choice == "4":
        r = new_items(items, kcap)
        items = r[0]
        kcap = r[1]
    elif choice == "5":
        running = False
    else:
        print("Pick a number from 1 to 5.")
print("Bye.")
```

### packing.eml

```eml
# P094 packing planner - items of whole-number sizes into bins of one
# capacity by three quick rules and by search for the fewest bins; and the
# 0/1 knapsack: the most value that fits, by dynamic programming, against
# taking the best value per unit of weight first.

def first_fit(sizes, cap, order):
    # The corpus case bin-packing-first-fit: each item, in the given order,
    # into the first bin it still fits in, a new bin if none. Returns the
    # bins as lists of item indices.
    [] => bins
    [] => room
    for i in order:
        -1 => chosen
        for b in [0:len(bins) - 1]:
            if chosen == -1 and room[b] >= sizes[i]:
                b => chosen
        if chosen == -1:
            bins + [[i]] => bins
            room + [cap - sizes[i]] => room
        else:
            bins[chosen] + [i] => bins[chosen]
            room[chosen] - sizes[i] => room[chosen]
    return bins

def best_fit(sizes, cap):
    # Each item into the bin it fits most tightly (least room left after),
    # the first such bin on a tie.
    [] => bins
    [] => room
    for i in [0:len(sizes) - 1]:
        -1 => chosen
        for b in [0:len(bins) - 1]:
            if room[b] >= sizes[i] and (chosen == -1 or room[b] < room[chosen]):
                b => chosen
        if chosen == -1:
            bins + [[i]] => bins
            room + [cap - sizes[i]] => room
        else:
            bins[chosen] + [i] => bins[chosen]
            room[chosen] - sizes[i] => room[chosen]
    return bins

def largest_first(sizes):
    # The item indices by size, largest first, keeping the order of equals.
    [0] * len(sizes) => order
    for i in [0:len(sizes) - 1]:
        i => order[i]
    for i in [1:len(order) - 1]:
        order[i] => x
        i - 1 => j
        while j >= 0 and sizes[order[j]] < sizes[x]:
            order[j] => order[j + 1]
            j - 1 => j
        x => order[j + 1]
    return order

def in_order(n):
    [0] * n => out
    for i in [0:n - 1]:
        i => out[i]
    return out

def fewest(sizes, cap):
    # The fewest bins, by search (as in the corpus case
    # subset-sum-backtracking): items largest first, each tried in every
    # bin it fits and in one new bin, giving up on any branch that already
    # uses as many bins as the best found. A bin count that reaches
    # ceil(total / cap) cannot be beaten, so the search stops there.
    largest_first(sizes) => order
    first_fit(sizes, cap, order) => best
    0 => total
    for s in sizes:
        total + s => total
    int((total + cap - 1 - (total + cap - 1) % cap) / cap) => bound
    if len(best) == bound:
        return best
    [best] => holder
    place(sizes, cap, order, 0, [], [], holder, bound)
    return holder[0]

def place(sizes, cap, order, k, bins, room, holder, bound):
    if len(holder[0]) == bound:
        return
    if k == len(order):
        if len(bins) < len(holder[0]):
            [] => copy
            for b in bins:
                copy + [b] => copy
            copy => holder[0]
        return
    order[k] => i
    for b in [0:len(bins) - 1]:
        if room[b] >= sizes[i]:
            bins[b] => old
            old + [i] => bins[b]
            room[b] - sizes[i] => room[b]
            place(sizes, cap, order, k + 1, bins, room, holder, bound)
            old => bins[b]
            room[b] + sizes[i] => room[b]
    if len(bins) + 1 < len(holder[0]):
        place(sizes, cap, order, k + 1, bins + [[i]], room + [cap - sizes[i]], holder, bound)

def knapsack(items, cap):
    # best[c] is the most value within weight c, item by item, going down
    # in c so each item is used at most once; took[k][c] records whether
    # item k was taken for c, to read the choice back. [value, items].
    [0] * (cap + 1) => best
    [] => took
    for k in [0:len(items) - 1]:
        items[k][0] => w
        items[k][1] => v
        [False] * (cap + 1) => row
        cap => c
        while c >= w:
            if best[c - w] + v > best[c]:
                best[c - w] + v => best[c]
                True => row[c]
            c - 1 => c
        took + [row] => took
    [] => chosen
    cap => c
    len(items) - 1 => k
    while k >= 0:
        if took[k][c]:
            [k] + chosen => chosen
            c - items[k][0] => c
        k - 1 => k
    return [best[cap], chosen]

def by_value(items, cap):
    # Greedy: best value per unit of weight first (compared by
    # cross-multiplication), taking each that still fits. [value, items].
    [0] * len(items) => order
    for i in [0:len(items) - 1]:
        i => order[i]
    for i in [1:len(order) - 1]:
        order[i] => x
        i - 1 => j
        while j >= 0 and items[order[j]][1] * items[x][0] < items[x][1] * items[order[j]][0]:
            order[j] => order[j + 1]
            j - 1 => j
        x => order[j + 1]
    0 => value
    cap => left
    [] => chosen
    for i in order:
        if items[i][0] <= left:
            left - items[i][0] => left
            value + items[i][1] => value
            chosen + [i] => chosen
    return [value, chosen]
```

Python projection of packing.eml:

```python
def first_fit(sizes, cap, order):
    bins = []
    room = []
    for i in order:
        chosen = -1
        for b in range(0, len(bins)):
            if chosen == -1 and room[b] >= sizes[i]:
                chosen = b
        if chosen == -1:
            bins = bins + [[i]]
            room = room + [cap - sizes[i]]
        else:
            bins[chosen] = bins[chosen] + [i]
            room[chosen] = room[chosen] - sizes[i]
    return bins

def best_fit(sizes, cap):
    bins = []
    room = []
    for i in range(0, len(sizes)):
        chosen = -1
        for b in range(0, len(bins)):
            if room[b] >= sizes[i] and (chosen == -1 or room[b] < room[chosen]):
                chosen = b
        if chosen == -1:
            bins = bins + [[i]]
            room = room + [cap - sizes[i]]
        else:
            bins[chosen] = bins[chosen] + [i]
            room[chosen] = room[chosen] - sizes[i]
    return bins

def largest_first(sizes):
    order = [0] * len(sizes)
    for i in range(0, len(sizes)):
        order[i] = i
    for i in range(1, len(order)):
        x = order[i]
        j = i - 1
        while j >= 0 and sizes[order[j]] < sizes[x]:
            order[j + 1] = order[j]
            j = j - 1
        order[j + 1] = x
    return order

def in_order(n):
    out = [0] * n
    for i in range(0, n):
        out[i] = i
    return out

def fewest(sizes, cap):
    order = largest_first(sizes)
    best = first_fit(sizes, cap, order)
    total = 0
    for s in sizes:
        total = total + s
    bound = int((total + cap - 1 - (total + cap - 1) % cap) / cap)
    if len(best) == bound:
        return best
    holder = [best]
    place(sizes, cap, order, 0, [], [], holder, bound)
    return holder[0]

def place(sizes, cap, order, k, bins, room, holder, bound):
    if len(holder[0]) == bound:
        return
    if k == len(order):
        if len(bins) < len(holder[0]):
            copy = []
            for b in bins:
                copy = copy + [b]
            holder[0] = copy
        return
    i = order[k]
    for b in range(0, len(bins)):
        if room[b] >= sizes[i]:
            old = bins[b]
            bins[b] = old + [i]
            room[b] = room[b] - sizes[i]
            place(sizes, cap, order, k + 1, bins, room, holder, bound)
            bins[b] = old
            room[b] = room[b] + sizes[i]
    if len(bins) + 1 < len(holder[0]):
        place(sizes, cap, order, k + 1, bins + [[i]], room + [cap - sizes[i]], holder, bound)

def knapsack(items, cap):
    best = [0] * (cap + 1)
    took = []
    for k in range(0, len(items)):
        w = items[k][0]
        v = items[k][1]
        row = [False] * (cap + 1)
        c = cap
        while c >= w:
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
                row[c] = True
            c = c - 1
        took = took + [row]
    chosen = []
    c = cap
    k = len(items) - 1
    while k >= 0:
        if took[k][c]:
            chosen = [k] + chosen
            c = c - items[k][0]
        k = k - 1
    return [best[cap], chosen]

def by_value(items, cap):
    order = [0] * len(items)
    for i in range(0, len(items)):
        order[i] = i
    for i in range(1, len(order)):
        x = order[i]
        j = i - 1
        while j >= 0 and items[order[j]][1] * items[x][0] < items[x][1] * items[order[j]][0]:
            order[j + 1] = order[j]
            j = j - 1
        order[j + 1] = x
    value = 0
    left = cap
    chosen = []
    for i in order:
        if items[i][0] <= left:
            left = left - items[i][0]
            value = value + items[i][1]
            chosen = chosen + [i]
    return [value, chosen]
```

## README

# P094 - Packing planner

Items into bins by three quick rules - First Fit, Best Fit and First Fit
Decreasing - against the fewest bins possible, found by search. And the
0/1 knapsack: the most value that fits, by dynamic programming, against
taking the best value per kilogram first.

- `main.eml` - the menu, reading items, and the reports
- `packing.eml` - the three rules, the search for the fewest bins, the
  knapsack table and the greedy rule

How each part works:

- First Fit, as in the corpus case `bin-packing-first-fit`: each item, in
  order, goes into the first bin it still fits in, or a new bin. On the
  corpus's items (5 7 4 2 8 3 1 into bins of 10) it uses 4 bins, though 3
  are enough: 8+2, 7+3, 5+4+1.
- Best Fit puts each item where it fits most tightly. First Fit
  Decreasing takes the largest first, which usually helps, but not always:
  with 8 4 2 6 3 3 in bins of 13 it uses 3, where 8+3+2 and 6+4+3 fill
  two.
- The fewest bins: a search, as in the corpus case
  `subset-sum-backtracking`. Items go largest first into every bin they
  fit and into one new bin, and any branch already using as many bins as
  the best found is dropped. When the count reaches the total divided by
  the capacity, rounded up, nothing can do better, so the search stops.
- The knapsack: for every weight up to the capacity, the most value that
  fits, item by item. Going down through the weights means each item is
  used at most once. A table of choices reads the items back. Taking the
  best value per kilogram first can be beaten: in a 50 kg knapsack it
  takes 10 kg worth 60 and 20 kg worth 100 (160), where 20 kg and 30 kg
  give 220.

What is checked: menu choices 1 to 5; a capacity of 1 to 100; 1 to 12
item sizes from 1 to the capacity; 1 to 12 knapsack items as weight-value
pairs, each 1 to 999. An empty answer cancels.

Sessions: `sessions/basic.in` gives:
- the corpus's items: 4, 4, 3 and 3 bins;
- the knapsack: 220 against the greedy 160;
- 8 4 2 6 3 3 in bins of 13, where even First Fit Decreasing misses the
  2 bins;
- a knapsack where the greedy rule is right (90), and ten items that every
  rule packs into the fewest bins.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- capacities 0 and 101; an item bigger than its bin, 13 items, letters;
- an odd number of knapsack numbers and a weight of 0; then cancels.

Built on the verified corpus cases `bin-packing-first-fit` (first fit,
and the bin it wastes) and `subset-sum-backtracking` (searching every
choice, dropping hopeless branches).