The 0/1 Knapsack Problem is a classic dynamic programming (DP) problem commonly found in algorithm competitions. This article presents five versions of the solution, starting from a basic brute-force approach and gradually evolving into a DP-based implementation.

Problem Definition

There are several items, each with aweightand a value:

struct Item {
  
Int
weight : 
Int
Int
  
Int
value : 
Int
Int
}

Now, given a list of items (items) and a knapsack capacity (capacity), select a subset of the items such that the total weight does not exceed the knapsack capacity, and the total value is maximized.

typealias 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
@list.T as List

let 
@list.T[Item]
items_1 : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item] = 
(arr : FixedArray[Item]) -> @list.T[Item]
@list.of([
  { 
Int
weight: 7, 
Int
value: 20 },
  { 
Int
weight: 4, 
Int
value: 10 },
  { 
Int
weight: 5, 
Int
value: 11 },
])

Take items_1 as an example. If the knapsack capacity is 10, the optimal solution is to select the last two items. Their combined weight is 4 + 5 = 9, and their total value is 10 + 11 = 21.

Note that items cannot be split. Therefore, greedily selecting the item with the highest value-to-weight ratio does not always yield the correct result.

For example, in the case above, if we pick only the first item (which has the highest ratio), we get 20 points in total, but the knapsack will be full and no other items can be added.

Problem Modeling

First, we define some basic objects and operations.

//A combination of items, referred to as "combination" throughout the article
struct Combination {
  
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item]
  
Int
total_weight : 
Int
Int
  
Int
total_value : 
Int
Int
}

//An empty combination
let 
Combination
empty_combination : 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination = {
  
@list.T[Item]
items: 
() -> @list.T[Item]
Creates an empty list
@list.empty(),
  
Int
total_weight: 0,
  
Int
total_value: 0,
}

//Add an item to a combination and return a new combination
fn 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination::
(self : Combination, item : Item) -> Combination
add(
Combination
self : 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination, 
Item
item : 
struct Item {
  weight: Int
  value: Int
}
Item) -> 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  {
    
@list.T[Item]
items: 
Combination
self.
@list.T[Item]
items.
(self : @list.T[Item], head : Item) -> @list.T[Item]
add(
Item
item),
    
Int
total_weight: 
Combination
self.
Int
total_weight 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
Item
item.
Int
weight,
    
Int
total_value: 
Combination
self.
Int
total_value 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
Item
item.
Int
value,
  }
}

//Two combinations are considered equal if they have the same total value
impl 
trait Eq {
  op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq for 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination with 
(self : Combination, other : Combination) -> Bool
op_equal(
Combination
self, 
Combination
other) {
  
Combination
self.
Int
total_value 
(self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 
Combination
other.
Int
total_value
}

//Compare two combinations by their total value
impl 
trait Compare {
  compare(Self, Self) -> Int
}
Trait for types whose elements are ordered
The return value of [compare] is:

zero, if the two arguments are equal
negative, if the first argument is smaller
positive, if the first argument is greater
Compare for 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination with 
(self : Combination, other : Combination) -> Int
compare(
Combination
self, 
Combination
other) {
  
Combination
self.
Int
total_value.
(self : Int, other : Int) -> Int
Compares two integers and returns their relative order.
Parameters:

self : The first integer to compare.
other : The second integer to compare against.
Returns an integer indicating the relative order:

A negative value if self is less than other
Zero if self equals other
A positive value if self is greater than other
Example:
  let a = 42
  let b = 24
  inspect(a.compare(b), content="1") // 42 > 24
  inspect(b.compare(a), content="-1") // 24 < 42
  inspect(a.compare(a), content="0") // 42 = 42
compare(
Combination
other.
Int
total_value)
}

Now, we can begin thinking about how to solve the problem.

1.Naive Enumeration

Enumeration is the most straightforward approach. By following the problem definition step by step, we can arrive at a solution:

1. Enumerate all possible combinations;
2. Filter out only the valid combinations-those that fit in the knapsack;
3. Select the one with the maximum total value.

Thanks to the two functions provided by our modeling, we can translate the three steps above directly into MoonBit code. The all_combinations function, which we'll implement later, has the type(List[Item]) -> List[Combination].

fn 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v1(
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item], 
Int
capacity : 
Int
Int) -> 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  
(items : @list.T[Item]) -> @list.T[Combination]
all_combinations(
@list.T[Item]
items)
  .
(self : @list.T[Combination], f : (Combination) -> Bool) -> @list.T[Combination]
Filter the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).filter(fn(x){ x % 2 == 0}), @list.of([2, 4]))
filter(fn(
Combination
comb) { 
Combination
comb.
Int
total_weight 
(self_ : Int, other : Int) -> Bool
<= 
Int
capacity })
  .
(self : @list.T[Combination]) -> Combination
unsafe_maximum()
}

Note that we use unsafe_maximum instead of maximum because we're taking the maximum of a non-empty list, and in this case, maximum will not return None.Since the problem guarantees that a solution exists (as long as capacity is non-negative), we can safely use unsafe_maximum. It skips the empty-list check but implicitly assumes the result will exist.

Now let's implement the enumeration step.Suppose all_combinations takes a list of items and returns a list of combinations, each representing a possible subset of those items. If this seems unclear at first, we can begin by looking at the definition of the list structure, which looks roughly like this:

enum List[A] {
  Empty
  More(A, tail~ : List[A])
}

In other words, a list has two possible forms:

1. An empty list, represented as Empty;
2. A non-empty list, represented as More, which contains the first element (A) and the rest of the list (tail: List[A]), which is itself also a list.

This structure gives us a hint for how to recursively build combinations:

• If the item list is empty, the only possible combination is the empty combination;
• Otherwise, there must be a first item item1 and a remaining list items_tail. In this case, we can:
  1. Recursively compute all combinations of items_tail, which represent combinations that do not include item1;
  2. For each of those, add item1 to form new combinations that do include it;
  3. Merge both sets to obtain all combinations of the original items list.

For example, if the item list is a, b, c, then the combinations can be divided into two parts:

Without a	With a (by adding a to the left side)
{ }	{ a }
{ b }	{ a, b }
{ c }	{ a, c }
{ b, c }	{ a, b, c }

fn 
(items : @list.T[Item]) -> @list.T[Combination]
all_combinations(
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item]) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match 
@list.T[Item]
items {
    
@list.T[Item]
Empty => 
(x : Combination) -> @list.T[Combination]
@list.singleton(
Combination
empty_combination)
    
(Item, @list.T[Item]) -> @list.T[Item]
More(
Item
item1, 
@list.T[Item]
tail=
@list.T[Item]
items_tail) => {
      let 
@list.T[Combination]
combs_without_item1 = 
(items : @list.T[Item]) -> @list.T[Combination]
all_combinations(
@list.T[Item]
items_tail)
      let 
@list.T[Combination]
combs_with_item1 = 
@list.T[Combination]
combs_without_item1.
(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.
(self : Combination, item : Item) -> Combination
add(
Item
item1))
      
@list.T[Combination]
combs_with_item1 
(self : @list.T[Combination], other : @list.T[Combination]) -> @list.T[Combination]
Concatenate two lists.
a + b equal to a.concat(b)
+ 
@list.T[Combination]
combs_without_item1
    }
  }
}

By using pattern matching (match), we've translated the five lines of logic above into MoonBit code for the first time, line by line.

2.Early Filtering: Enumerate Only Valid Combinations

In the first version, generating all combinations and filtering out those that fit in the knapsack were two separate steps.During the enumeration process, many invalid combinations were generated-combinations that had already exceeded the knapsack capacity but were still extended with more items.If we filter them earlier, we can avoid generating many unnecessary combinations on top of invalid ones, which is clearly more efficient.Looking at the code, we see that invalid combinations are only produced during .map(_.add(item1)).So we can optimize by only adding item1 to combinations that can still fit it.

We now rename all_combinations to all_combinations_valid, which returns only combinations that can actually fit in the knapsack. The generation and filtering processes are now interleaved.

fn 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
  
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item],
  
Int
capacity : 
Int
Int // Add capacity as a parameter because filtering requires it
) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match 
@list.T[Item]
items {
    
@list.T[Item]
Empty => 
(x : Combination) -> @list.T[Combination]
@list.singleton(
Combination
empty_combination) // An empty combination is always valid
    
(Item, @list.T[Item]) -> @list.T[Item]
More(
Item
item1, 
@list.T[Item]
tail=
@list.T[Item]
items_tail) => {
      // Recursively obtain combinations without this item (by assumption, all valid)
      let 
@list.T[Combination]
valid_combs_without_item1 = 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
        
@list.T[Item]
items_tail, 
Int
capacity,
      )
      // Add item1 to valid combinations that can still hold it
      let 
@list.T[Combination]
valid_combs_with_item1 = 
@list.T[Combination]
valid_combs_without_item1
        .
(self : @list.T[Combination], f : (Combination) -> Bool) -> @list.T[Combination]
Filter the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).filter(fn(x){ x % 2 == 0}), @list.of([2, 4]))
filter(fn(
Combination
comb) { 
Combination
comb.
Int
total_weight 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
Item
item1.
Int
weight 
(self_ : Int, other : Int) -> Bool
<= 
Int
capacity })
        .
(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.
(self : Combination, item : Item) -> Combination
add(
Item
item1))
      // Both parts are valid, so we return their union
      
@list.T[Combination]
valid_combs_with_item1 
(self : @list.T[Combination], other : @list.T[Combination]) -> @list.T[Combination]
Concatenate two lists.
a + b equal to a.concat(b)
+ 
@list.T[Combination]
valid_combs_without_item1
    }
  }
}

This structure naturally supports inductive reasoning, making it easy to prove the correctness of all_combinations_valid-it indeed returns only valid combinations.

Since all_combinations_valid already returns only valid combinations, we no longer need to filter in solve.We simply remove the filter from solve:

fn 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v2(
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item], 
Int
capacity : 
Int
Int) -> 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
@list.T[Item]
items, 
Int
capacity).
(self : @list.T[Combination]) -> Combination
unsafe_maximum()
}

3.Maintain Order to Enable Early Termination

In the previous version, to construct new combinations, we needed to iterate over every combination in valid_combs_without_item1.

But we can observe: if item1 cannot be added to a certain combination, then it definitely cannot be added to any combination with a greater total weight than that one. In other words, if valid_combs_without_item1 is sorted in ascending order of total weight, then we don't need to traverse it entirely during filtering.

During filtering, as soon as we encounter a combination that can't fit item1, we can immediately discard the remaining combinations.Since this logic is common, the standard library provides a function called take_while, which we use to replace filter.

To make valid_combs_without_item1 sorted, we could use a sorting algorithm-but that would require traversing the entire list, which defeats the purpose.Therefore, we adopt a different approach: ensure that the list returned by all_combinations_valid is already sorted in ascending order.

This requires a leap of faith via recursion:

fn 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
  
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item],
  
Int
capacity : 
Int
Int
) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match 
@list.T[Item]
items {
    
@list.T[Item]
Empty => 
(x : Combination) -> @list.T[Combination]
@list.singleton(
Combination
empty_combination) // A single-element list is naturally in ascending order.
    
(Item, @list.T[Item]) -> @list.T[Item]
More(
Item
item1, 
@list.T[Item]
tail=
@list.T[Item]
items_tail) => {
      // We assume that all_combinations_valid_ordered returns a list sorted in ascending order (inductive hypothesis).
      let 
@list.T[Combination]
valid_combs_without_item1 = 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
        
@list.T[Item]
items_tail, 
Int
capacity,
      )
      // Then valid_combs_with_item1 is also in ascending order, because taking a prefix of an ascending list and adding the same weight to each element still yields an ascending list by total weight.
      let 
@list.T[Combination]
valid_combs_with_item1 = 
@list.T[Combination]
valid_combs_without_item1
        .
(self : @list.T[Combination], p : (Combination) -> Bool) -> @list.T[Combination]
Take the longest prefix of a list of elements that satisfies a given predicate.
Example
  let ls = @list.from_array([1, 2, 3, 4])
  let r = ls.take_while(fn(x) { x < 3 })
  assert_eq(r, @list.of([1, 2]))
take_while(fn(
Combination
comb) { 
Combination
comb.
Int
total_weight 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
Item
item1.
Int
weight 
(self_ : Int, other : Int) -> Bool
<= 
Int
capacity })
        .
(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.
(self : Combination, item : Item) -> Combination
add(
Item
item1))
      // Now, we only need to ensure that the merged result is also sorted in ascending order to maintain our initial assumption.
      
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(
@list.T[Combination]
valid_combs_with_item1, 
@list.T[Combination]
valid_combs_without_item1)
    }
  }
}

The final task is to implement the function merge_keep_order, which merges two ascending lists into one ascending list:

fn 
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(
  
@list.T[Combination]
a : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination],
  
@list.T[Combination]
b : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination]
) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match (
@list.T[Combination]
a, 
@list.T[Combination]
b) {
    (
@list.T[Combination]
Empty, 
@list.T[Combination]
another) | (
@list.T[Combination]
another, 
@list.T[Combination]
Empty) => 
@list.T[Combination]
another
    (
(Combination, @list.T[Combination]) -> @list.T[Combination]
More(
Combination
a1, 
@list.T[Combination]
tail=
@list.T[Combination]
a_tail), 
(Combination, @list.T[Combination]) -> @list.T[Combination]
More(
Combination
b1, 
@list.T[Combination]
tail=
@list.T[Combination]
b_tail)) =>
      // If a1 is lighter than b1, and b1 is part of an ascending list, then:
      //   a1 is lighter than all combinations in b
      // Since list a is also in ascending order
      //   a1 is also lighter than all combinations in a_tail
      // Therefore, a1 is the smallest among all elements in a and b
      if 
Combination
a1.
Int
total_weight 
(self_ : Int, other : Int) -> Bool
< 
Combination
b1.
Int
total_weight {
        // We first recursively merge the rest of the list, then prepend a1
        
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(
@list.T[Combination]
a_tail, 
@list.T[Combination]
b).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(
Combination
a1)
      } else { //
        
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(
@list.T[Combination]
a, 
@list.T[Combination]
b_tail).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(
Combination
b1)
      }
  }
}

Although it might seem a bit verbose, I still want to point this out: by following a case-based analysis aligned with the structure of the code, it's actually easy to prove the correctness of all_combinations_valid_ordered and merge_keep_order - they do return a sorted list.

For an ascending list, the maximum element is simply the last one. So we replaced unsafe_maximum with unsafe_last.

fn 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v3(
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item], 
Int
capacity : 
Int
Int) -> 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
@list.T[Item]
items, 
Int
capacity).
(self : @list.T[Combination]) -> Combination
unsafe_last()
}

Looking back, this version of the optimization might not seem like a big win - after all, we still have to traverse the entire list during the merge. That was my initial impression too, but I later discovered something unexpected.

4.Removing Redundant Combinations with Equal Weights for Optimal Time Complexity

So far, the optimizations we've made haven't addressed time complexity, but they've laid the groundwork for this next step. Now let's consider the algorithm's time complexity.

In the worst case (e.g., when the knapsack is large enough to hold everything), the combination list returned by all_combinations can contain up to $2^{number of items}$ elements. This results in an exponential time complexity, especially since all_combinations is called multiple times, each time returning a potentially large list.

To reduce the time complexity, we need to limit the length of the candidate combination list. This is based on a simple observation: if two combinations have the same total weight, the one with the higher total value is always better. Therefore, we don't need to keep both in the list.

By eliminating these redundant combinations, the list length will never exceed the knapsack's capacity (thanks to the pigeonhole principle). This optimization reduces the algorithm's time complexity to $\mathcal{O}(number of items \times capacity)$. Upon reviewing the code, the only place where redundant combinations may still be introduced is the else branch of merge_keep_order. To prevent this, we just need to make a small modification to that section.

fnalias 
(x : T, y : T) -> T
Compares and returns the maximum of two values.
Returns the second argument if the comparison determines them to be equal.
Examples
  assert_eq(@math.maximum(1, 2), 2)
  assert_eq(@math.maximum(2, 2), 2)
@math.maximum

fn 
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
  
@list.T[Combination]
a : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination],
  
@list.T[Combination]
b : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination]
) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match (
@list.T[Combination]
a, 
@list.T[Combination]
b) {
    (
@list.T[Combination]
Empty, 
@list.T[Combination]
another) | (
@list.T[Combination]
another, 
@list.T[Combination]
Empty) => 
@list.T[Combination]
another
    (
(Combination, @list.T[Combination]) -> @list.T[Combination]
More(
Combination
a1, 
@list.T[Combination]
tail=
@list.T[Combination]
a_tail), 
(Combination, @list.T[Combination]) -> @list.T[Combination]
More(
Combination
b1, 
@list.T[Combination]
tail=
@list.T[Combination]
b_tail)) =>
      if 
Combination
a1.
Int
total_weight 
(self_ : Int, other : Int) -> Bool
< 
Combination
b1.
Int
total_weight {
        
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
@list.T[Combination]
a_tail, 
@list.T[Combination]
b).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(
Combination
a1)
      } else if 
Combination
a1.
Int
total_weight 
(self_ : Int, other : Int) -> Bool
> 
Combination
b1.
Int
total_weight {
        
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
@list.T[Combination]
a, 
@list.T[Combination]
b_tail).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(
Combination
b1)
      } else { // "In this case, a1 and b1 have the same weight, creating a duplicate. We keep the one with the higher total value."
        let 
Combination
better = 
(x : Combination, y : Combination) -> Combination
Compares and returns the maximum of two values.
Returns the second argument if the comparison determines them to be equal.
Examples
  assert_eq(@math.maximum(1, 2), 2)
  assert_eq(@math.maximum(2, 2), 2)
maximum(
Combination
a1, 
Combination
b1)
        
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
@list.T[Combination]
a_tail, 
@list.T[Combination]
b_tail).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(
Combination
better)
      }
  }
}

Simply replace the corresponding parts with all_combinations_valid_ordered_nodup (arguably the longest function name I've ever written) and solve_v4.

fn 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup(
  
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item],
  
Int
capacity : 
Int
Int
) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match 
@list.T[Item]
items {
    
@list.T[Item]
Empty => 
(x : Combination) -> @list.T[Combination]
@list.singleton(
Combination
empty_combination)
    
(Item, @list.T[Item]) -> @list.T[Item]
More(
Item
item1, 
@list.T[Item]
tail=
@list.T[Item]
items_tail) => {
      let 
@list.T[Combination]
combs_without_item1 = 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup(
        
@list.T[Item]
items_tail, 
Int
capacity,
      )
      let 
@list.T[Combination]
combs_with_item1 = 
@list.T[Combination]
combs_without_item1
        .
(self : @list.T[Combination], p : (Combination) -> Bool) -> @list.T[Combination]
Take the longest prefix of a list of elements that satisfies a given predicate.
Example
  let ls = @list.from_array([1, 2, 3, 4])
  let r = ls.take_while(fn(x) { x < 3 })
  assert_eq(r, @list.of([1, 2]))
take_while(fn(
Combination
comb) { 
Combination
comb.
Int
total_weight 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
Item
item1.
Int
weight 
(self_ : Int, other : Int) -> Bool
<= 
Int
capacity })
        .
(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.
(self : Combination, item : Item) -> Combination
add(
Item
item1))
      
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
@list.T[Combination]
combs_with_item1, 
@list.T[Combination]
combs_without_item1)
    }
  }
}

fn 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v4(
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item], 
Int
capacity : 
Int
Int) -> 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup(
@list.T[Item]
items, 
Int
capacity).
(self : @list.T[Combination]) -> Combination
unsafe_last()
}

At this point, we've essentially reinvented the dynamic programming solution for the 0/1 knapsack problem.

Conclusion

This article's content came from a sudden idea I had one morning while lying in bed. From the first to the fourth version, all code was written entirely on my phone without any debugging-yet correctness was easily guaranteed. Compared to conventional solutions often seen in algorithm competitions, the functional programming style used here brings the following advantages:

1. No loops, only recursion and structural decomposition. To extract elements from a list, pattern matching (match) is required, which naturally prompts consideration of empty cases and expresses intent more clearly than initializing a DP array.
2. Composition of higher-order functions. Standard functions like filter, take_while, map, and maximum replace boilerplate loops (for, while), making the traversal purpose clearer at a glance.
3. Declarative code. The later versions of the solution are direct translations of the first one. Rather than just implementing a solution, the code describes the problem itself. This ensures the correctness of the first version. Each subsequent improvement was made without affecting the correctness, allowing for a safe and iterative process.

Of course, this solution doesn't apply state space compression, so a tradeoff between readability and efficiency remains. The functional style is slightly idealistic but still leaves room for many optimizations. A future direction would be to convert the list structure into a tree, exploiting the fact that functions only pass two argument groups throughout execution-possibly even a single value. This could reduce space complexity to O(capacity), though it's beyond the scope of this article. We believe the approach here offers a beginner-friendly and understandable way to write correct code.

Appendix

Further Optimization Details

Given that the order of items does not affect the total value of the result, we can convert all_combinations into a tail-recursive version.

Additionally, since the list produced by take_while is immediately discarded after being passed to map, certain syntax-level techniques can be used to avoid creating this temporary list altogether.

fn 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_loop(
  
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item],
  
Int
capacity : 
Int
Int
) -> 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  loop 
@list.T[Item]
items, 
(x : Combination) -> @list.T[Combination]
@list.singleton(
Combination
empty_combination) {
    
@list.T[Item]
Empty, 
@list.T[Combination]
combs_so_far => 
@list.T[Combination]
combs_so_far
    
(Item, @list.T[Item]) -> @list.T[Item]
More(
Item
item1, 
@list.T[Item]
tail=
@list.T[Item]
items_tail), 
@list.T[Combination]
combs_so_far => {
      let 
@list.T[Combination]
combs_without_item1 = 
@list.T[Combination]
combs_so_far
      let 
@list.T[Combination]
combs_with_item1 = 
@list.T[Combination]
combs_without_item1
        .
(self : @list.T[Combination]) -> Iter[Combination]
iter()
        .
(self : Iter[Combination], f : (Combination) -> Bool) -> Iter[Combination]
Takes elements from the iterator as long as the predicate function returns true.
Type Parameters

T: The type of the elements in the iterator.
Arguments

self - The input iterator.
f - The predicate function that determines whether an element should be taken.
Returns
A new iterator that contains the elements as long as the predicate function returns true.
take_while(fn(
Combination
comb) { 
Combination
comb.
Int
total_weight 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
Item
item1.
Int
weight 
(self_ : Int, other : Int) -> Bool
<= 
Int
capacity })
        .
(self : Iter[Combination], f : (Combination) -> Combination) -> Iter[Combination]
Transforms the elements of the iterator using a mapping function.
Type Parameters

T: The type of the elements in the iterator.
R: The type of the transformed elements.
Arguments

self - The input iterator.
f - The mapping function that transforms each element of the iterator.
Returns
A new iterator that contains the transformed elements.
map(_.
(self : Combination, item : Item) -> Combination
add(
Item
item1))
        |> 
(iter : Iter[Combination]) -> @list.T[Combination]
Convert the iterator into a list. Preserves order of elements.
If the order of elements is not important, use from_iter_rev instead.
@list.from_iter
      continue 
@list.T[Item]
items_tail,
        
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
@list.T[Combination]
combs_with_item1, 
@list.T[Combination]
combs_without_item1)
    }
  }
}

fn 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v5(
@list.T[Item]
items : 
enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[
struct Item {
  weight: Int
  value: Int
}
Item], 
Int
capacity : 
Int
Int) -> 
struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_loop(
@list.T[Item]
items, 
Int
capacity).
(self : @list.T[Combination]) -> Combination
unsafe_last()
}

Side Notes

1. In the first version, the Combination generated by all_combinations(items) even contains one more node than More, making it a true master of linked list node reuse.
2. An ascending order can't be treated as "broken" order, so the corresponding take_while must be converted to drop_while. When using an array, we can directly cut segments via binary_search on indices.
3. If you're interested, consider how to generalize the above approach to various other knapsack problems.
4. The original name of all_combinations_loop was: generate_all_ordered_combination_that_fit_in_backpack_list_without_duplicates_using_loop.

Test

test {
  for 
(@list.T[Item], Int) -> Combination
solve in [
(items : @list.T[Item], capacity : Int) -> Combination
solve_v1, 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v2, 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v3, 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v4, 
(items : @list.T[Item], capacity : Int) -> Combination
solve_v5] {
    
(a : Int, b : Int, loc~ : SourceLoc = _) -> Unit raise Error
Asserts that two values are equal. If they are not equal, raises a failure
with a message containing the source location and the values being compared.
Parameters:

a : First value to compare.
b : Second value to compare.
loc : Source location information to include in failure messages. This is
usually automatically provided by the compiler.
Throws a Failure error if the values are not equal, with a message showing
the location of the failing assertion and the actual values that were
compared.
Example:
  assert_eq(1, 1)
  assert_eq("hello", "hello")
assert_eq(
(@list.T[Item], Int) -> Combination
solve(
@list.T[Item]
items_1, 10).
Int
total_value, 21)
  }
}