Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 reportspacking.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (26 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (15 lines)
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
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (packing.py)
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]