Knapsack
Choose items, each at most once, to carry the greatest total value without going over a weight limit.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: knapsack.nomi
//# The 0/1 knapsack problem: the most value of items that fits a weight
//# limit.
/// Something that could go in the knapsack.
pub struct Item
weight: Int
value: Int
end
/// The greatest total value of `items`, each taken at most once, whose
/// weights add up to no more than `maximum_weight`.
pub fn maximum_value(items: List<Item>, maximum_weight: Int) -> Int
nothing =
Iter.repeat(0)
|> Iter.take(maximum_weight + 1)
|> Iter.to_vector()
items
|> Iter.reduce(nothing, consider)
|> Vector.get(maximum_weight)!
end
/// The best value for each capacity from 0 to the maximum once `item` may be
/// taken, given `best`, the best value for each capacity without it.
fn consider(best: Vector<Int>, item: Item) -> Vector<Int>
best
|> Iter.with_index()
|> Iter.map(fn (capacity, without) ->
if capacity < item.weight then
without
else
Int.max(without, Vector.get(best, capacity - item.weight)! + item.value)
end
end)
|> Iter.to_vector()
end
// FILE: knapsack_test.nomi
import knapsack.{self, Item}
test "maximum value"
cases: List<(String, Int, List<Item>, Int)> = [
("no items", 100, [], 0),
("one item, too heavy", 10, [{weight: 100, value: 1}], 0),
(
"five items (cannot be greedy by weight)",
10,
[
{weight: 2, value: 5},
{weight: 2, value: 5},
{weight: 2, value: 5},
{weight: 2, value: 5},
{weight: 10, value: 21},
],
21,
),
(
"five items (cannot be greedy by value)",
10,
[
{weight: 2, value: 20},
{weight: 2, value: 20},
{weight: 2, value: 20},
{weight: 2, value: 20},
{weight: 10, value: 50},
],
80,
),
(
"example knapsack",
10,
[
{weight: 5, value: 10},
{weight: 4, value: 40},
{weight: 6, value: 30},
{weight: 4, value: 50},
],
90,
),
(
"8 items",
104,
[
{weight: 25, value: 350},
{weight: 35, value: 400},
{weight: 45, value: 450},
{weight: 5, value: 20},
{weight: 25, value: 70},
{weight: 3, value: 8},
{weight: 2, value: 5},
{weight: 2, value: 5},
],
900,
),
(
"15 items",
750,
[
{weight: 70, value: 135},
{weight: 73, value: 139},
{weight: 77, value: 149},
{weight: 80, value: 150},
{weight: 82, value: 156},
{weight: 87, value: 163},
{weight: 90, value: 173},
{weight: 94, value: 184},
{weight: 98, value: 192},
{weight: 106, value: 201},
{weight: 110, value: 210},
{weight: 113, value: 214},
{weight: 115, value: 221},
{weight: 118, value: 229},
{weight: 120, value: 240},
],
1458,
),
]
subtests cases, (description, maximum_weight, items, expected), description
assert knapsack.maximum_value(items, maximum_weight) == expected
end
endok maximum value (7 cases)
test result: ok. 7 passed, 0 failed
How it’s written
Section titled “How it’s written”- An item is a struct,
Item, with the canonical data’sweightandvaluefields, and the test rows write each as{weight: 2, value: 5}under an annotated table. - The answer is the 0/1 knapsack’s dynamic programming: a
Vectorof the best value for every capacity from 0 to the limit, rebuilt once per item byconsider. The capacity is the index, soIter.with_indexreads it beside the value. Trying every subset would be 2^15 subsets for the largest case; the table is 15 rows of 751 entries. - Each row is a new
Vectorbuilt from the one before it, read throughbest, so no entry is overwritten before a later capacity reads it, the trap an in-place version must avoid by running the capacities downwards. - The fold names its step,
items |> Iter.reduce(nothing, consider)(style §33), and the answer is the final row’s entry for the limit, read in the same pipe. The empty row isIter.repeat(0)cut to the limit plus one. - The seven current canonical cases are one
subteststable named by the description column. The first “no items” case, whose items are a JSON object, is left out: the second, with an empty list, reimplements it.