1173 Advanced

Knapsack Problem — Dynamic Programming (Functional)

Dynamic ProgrammingFunctional Algorithms

Tutorial

The Problem

Given a list of items, each with a weight and a value, find the maximum total value that can fit into a knapsack of a given capacity (0/1 knapsack: each item taken at most once).

🎯 Learning Outcomes

• How OCaml's Hashtbl memoization maps to Rust's HashMap for top-down DP

• How recursive functional decomposition translates into explicit fn helpers in Rust (no closures capturing &mut)

• How the same problem can be solved with a bottom-up DP table or a space-optimised rolling array

• When rev() on a range prevents double-counting items in the rolling approach

🦀 The Rust Way

Rust cannot have a mutable borrow (&mut HashMap) inside a recursive closure that also borrows items, so the inner function is lifted to a free fn that receives all dependencies as parameters. The bottom-up variant uses a 2-D Vec<Vec<usize>>, while the rolling variant saves memory by iterating capacity in reverse with .rev().

Code Example

pub fn knapsack(items: &[(usize, usize)], capacity: usize) -> usize {
    let mut cache = HashMap::new();
    solve(items, 0, capacity, &mut cache)
}

fn solve(
    items: &[(usize, usize)],
    i: usize,
    cap: usize,
    cache: &mut HashMap<(usize, usize), usize>,
) -> usize {
    if i >= items.len() || cap == 0 {
        return 0;
    }
    if let Some(&v) = cache.get(&(i, cap)) {
        return v;
    }
    let (w, v) = items[i];
    let without = solve(items, i + 1, cap, cache);
    let with_item = if w <= cap {
        v + solve(items, i + 1, cap - w, cache)
    } else {
        0
    };
    let best = without.max(with_item);
    cache.insert((i, cap), best);
    best
}

let knapsack items capacity =
  let n = List.length items in
  let items = Array.of_list items in
  let cache = Hashtbl.create 256 in
  let rec solve i cap =
    if i >= n || cap <= 0 then 0
    else match Hashtbl.find_opt cache (i, cap) with
    | Some v -> v
    | None ->
      let (w, v) = items.(i) in
      let without = solve (i+1) cap in
      let with_item = if w <= cap then v + solve (i+1) (cap - w) else 0 in
      let best = max without with_item in
      Hashtbl.add cache (i, cap) best;
      best
  in solve 0 capacity

Key Differences

Mutable captured state: OCaml closures freely capture mutable Hashtbl; Rust requires

lifting the recursive helper to a free function to satisfy the borrow checker.

Tuple patterns: OCaml uses let (w, v) = items.(i) destructuring; Rust uses the same

syntax let (w, v) = items[i] on a slice dereference.

Max combinator: OCaml uses max without with_item; Rust uses without.max(with_item),

a method on usize, avoiding a free function import.

Space optimisation: The rolling-array approach is natural in Rust with (w..=capacity).rev()

— iterating high-to-low ensures each item is used at most once per pass.

OCaml Approach

OCaml defines a local recursive function solve that closes over the items array and the hash table, checking the cache before recursing and storing results after. The functional style naturally expresses the two branches (take vs. skip an item) as a let … in chain.

Full Source

use std::collections::HashMap;

/// Solution 1: Idiomatic Rust — memoized recursion with HashMap cache
/// Mirrors the OCaml top-down DP approach (hashtable memoization).
pub fn knapsack(items: &[(usize, usize)], capacity: usize) -> usize {
    let mut cache = HashMap::new();
    solve(items, 0, capacity, &mut cache)
}

fn solve(
    items: &[(usize, usize)],
    i: usize,
    cap: usize,
    cache: &mut HashMap<(usize, usize), usize>,
) -> usize {
    if i >= items.len() || cap == 0 {
        return 0;
    }
    if let Some(&v) = cache.get(&(i, cap)) {
        return v;
    }
    let (w, v) = items[i];
    let without = solve(items, i + 1, cap, cache);
    let with_item = if w <= cap {
        v + solve(items, i + 1, cap - w, cache)
    } else {
        0
    };
    let best = without.max(with_item);
    cache.insert((i, cap), best);
    best
}

/// Solution 2: Bottom-up DP table — classic iterative Rust style
/// Builds a 2D table: dp[i][c] = best value using items[0..i] with capacity c.
pub fn knapsack_bottom_up(items: &[(usize, usize)], capacity: usize) -> usize {
    let n = items.len();
    // dp[i][c]: max value using first i items with capacity c
    let mut dp = vec![vec![0usize; capacity + 1]; n + 1];
    for i in 1..=n {
        let (w, v) = items[i - 1];
        for c in 0..=capacity {
            dp[i][c] = if w <= c {
                dp[i - 1][c].max(v + dp[i - 1][c - w])
            } else {
                dp[i - 1][c]
            };
        }
    }
    dp[n][capacity]
}

/// Solution 3: Bottom-up DP with a single rolling row (space-optimised)
/// Iterates capacity in reverse to avoid overwriting values we still need.
pub fn knapsack_rolling(items: &[(usize, usize)], capacity: usize) -> usize {
    let mut dp = vec![0usize; capacity + 1];
    for &(w, v) in items {
        // Traverse high → low so each item is counted at most once
        for c in (w..=capacity).rev() {
            dp[c] = dp[c].max(v + dp[c - w]);
        }
    }
    dp[capacity]
}

#[cfg(test)]
mod tests {
    use super::*;

    const ITEMS: &[(usize, usize)] = &[(2, 3), (3, 4), (4, 5), (5, 6)];

    #[test]
    fn test_empty_items() {
        assert_eq!(knapsack(&[], 10), 0);
        assert_eq!(knapsack_bottom_up(&[], 10), 0);
        assert_eq!(knapsack_rolling(&[], 10), 0);
    }

    #[test]
    fn test_zero_capacity() {
        assert_eq!(knapsack(ITEMS, 0), 0);
        assert_eq!(knapsack_bottom_up(ITEMS, 0), 0);
        assert_eq!(knapsack_rolling(ITEMS, 0), 0);
    }

    #[test]
    fn test_ocaml_example() {
        // OCaml example: items = [(2,3);(3,4);(4,5);(5,6)], capacity = 8
        // Optimal: take (3,4) + (5,6) → weight=8, value=10
        assert_eq!(knapsack(ITEMS, 8), 10);
        assert_eq!(knapsack_bottom_up(ITEMS, 8), 10);
        assert_eq!(knapsack_rolling(ITEMS, 8), 10);
    }

    #[test]
    fn test_single_item_fits() {
        // weight=3 does NOT fit in capacity=2
        assert_eq!(knapsack(&[(3, 7)], 2), 0);
        assert_eq!(knapsack_bottom_up(&[(3, 7)], 2), 0);
        assert_eq!(knapsack_rolling(&[(3, 7)], 2), 0);
        // weight=3 fits exactly in capacity=3
        assert_eq!(knapsack(&[(3, 7)], 3), 7);
        assert_eq!(knapsack_bottom_up(&[(3, 7)], 3), 7);
        assert_eq!(knapsack_rolling(&[(3, 7)], 3), 7);
    }

    #[test]
    fn test_all_items_fit() {
        // Total weight = 2+3+4+5 = 14, capacity 20 — take everything
        let total_value: usize = ITEMS.iter().map(|&(_, v)| v).sum();
        assert_eq!(knapsack(ITEMS, 20), total_value);
        assert_eq!(knapsack_bottom_up(ITEMS, 20), total_value);
        assert_eq!(knapsack_rolling(ITEMS, 20), total_value);
    }

    #[test]
    fn test_small_capacity() {
        // Only item (2,3) fits within capacity 2
        assert_eq!(knapsack(ITEMS, 2), 3);
        assert_eq!(knapsack_bottom_up(ITEMS, 2), 3);
        assert_eq!(knapsack_rolling(ITEMS, 2), 3);
    }

    #[test]
    fn test_all_variants_agree() {
        for cap in 0..=15 {
            let a = knapsack(ITEMS, cap);
            let b = knapsack_bottom_up(ITEMS, cap);
            let c = knapsack_rolling(ITEMS, cap);
            assert_eq!(a, b, "mismatch at cap={cap}: top-down={a} bottom-up={b}");
            assert_eq!(b, c, "mismatch at cap={cap}: bottom-up={b} rolling={c}");
        }
    }
}

let knapsack items capacity =
  let n = List.length items in
  let items = Array.of_list items in
  let cache = Hashtbl.create 256 in
  let rec solve i cap =
    if i >= n || cap <= 0 then 0
    else match Hashtbl.find_opt cache (i, cap) with
    | Some v -> v
    | None ->
      let (w, v) = items.(i) in
      let without = solve (i+1) cap in
      let with_item = if w <= cap then v + solve (i+1) (cap - w) else 0 in
      let best = max without with_item in
      Hashtbl.add cache (i, cap) best;
      best
  in solve 0 capacity

let () =
  let items = [(2,3);(3,4);(4,5);(5,6)] in
  Printf.printf "Max value: %d\n" (knapsack items 8)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    const ITEMS: &[(usize, usize)] = &[(2, 3), (3, 4), (4, 5), (5, 6)];

    #[test]
    fn test_empty_items() {
        assert_eq!(knapsack(&[], 10), 0);
        assert_eq!(knapsack_bottom_up(&[], 10), 0);
        assert_eq!(knapsack_rolling(&[], 10), 0);
    }

    #[test]
    fn test_zero_capacity() {
        assert_eq!(knapsack(ITEMS, 0), 0);
        assert_eq!(knapsack_bottom_up(ITEMS, 0), 0);
        assert_eq!(knapsack_rolling(ITEMS, 0), 0);
    }

    #[test]
    fn test_ocaml_example() {
        // OCaml example: items = [(2,3);(3,4);(4,5);(5,6)], capacity = 8
        // Optimal: take (3,4) + (5,6) → weight=8, value=10
        assert_eq!(knapsack(ITEMS, 8), 10);
        assert_eq!(knapsack_bottom_up(ITEMS, 8), 10);
        assert_eq!(knapsack_rolling(ITEMS, 8), 10);
    }

    #[test]
    fn test_single_item_fits() {
        // weight=3 does NOT fit in capacity=2
        assert_eq!(knapsack(&[(3, 7)], 2), 0);
        assert_eq!(knapsack_bottom_up(&[(3, 7)], 2), 0);
        assert_eq!(knapsack_rolling(&[(3, 7)], 2), 0);
        // weight=3 fits exactly in capacity=3
        assert_eq!(knapsack(&[(3, 7)], 3), 7);
        assert_eq!(knapsack_bottom_up(&[(3, 7)], 3), 7);
        assert_eq!(knapsack_rolling(&[(3, 7)], 3), 7);
    }

    #[test]
    fn test_all_items_fit() {
        // Total weight = 2+3+4+5 = 14, capacity 20 — take everything
        let total_value: usize = ITEMS.iter().map(|&(_, v)| v).sum();
        assert_eq!(knapsack(ITEMS, 20), total_value);
        assert_eq!(knapsack_bottom_up(ITEMS, 20), total_value);
        assert_eq!(knapsack_rolling(ITEMS, 20), total_value);
    }

    #[test]
    fn test_small_capacity() {
        // Only item (2,3) fits within capacity 2
        assert_eq!(knapsack(ITEMS, 2), 3);
        assert_eq!(knapsack_bottom_up(ITEMS, 2), 3);
        assert_eq!(knapsack_rolling(ITEMS, 2), 3);
    }

    #[test]
    fn test_all_variants_agree() {
        for cap in 0..=15 {
            let a = knapsack(ITEMS, cap);
            let b = knapsack_bottom_up(ITEMS, cap);
            let c = knapsack_rolling(ITEMS, cap);
            assert_eq!(a, b, "mismatch at cap={cap}: top-down={a} bottom-up={b}");
            assert_eq!(b, c, "mismatch at cap={cap}: bottom-up={b} rolling={c}");
        }
    }
}

Deep Comparison

OCaml vs Rust: Knapsack Problem — Dynamic Programming (Functional)

Side-by-Side Code

OCaml

let knapsack items capacity =
  let n = List.length items in
  let items = Array.of_list items in
  let cache = Hashtbl.create 256 in
  let rec solve i cap =
    if i >= n || cap <= 0 then 0
    else match Hashtbl.find_opt cache (i, cap) with
    | Some v -> v
    | None ->
      let (w, v) = items.(i) in
      let without = solve (i+1) cap in
      let with_item = if w <= cap then v + solve (i+1) (cap - w) else 0 in
      let best = max without with_item in
      Hashtbl.add cache (i, cap) best;
      best
  in solve 0 capacity

Rust (idiomatic — memoized top-down, mirrors OCaml)

pub fn knapsack(items: &[(usize, usize)], capacity: usize) -> usize {
    let mut cache = HashMap::new();
    solve(items, 0, capacity, &mut cache)
}

fn solve(
    items: &[(usize, usize)],
    i: usize,
    cap: usize,
    cache: &mut HashMap<(usize, usize), usize>,
) -> usize {
    if i >= items.len() || cap == 0 {
        return 0;
    }
    if let Some(&v) = cache.get(&(i, cap)) {
        return v;
    }
    let (w, v) = items[i];
    let without = solve(items, i + 1, cap, cache);
    let with_item = if w <= cap {
        v + solve(items, i + 1, cap - w, cache)
    } else {
        0
    };
    let best = without.max(with_item);
    cache.insert((i, cap), best);
    best
}

Rust (bottom-up DP table)

pub fn knapsack_bottom_up(items: &[(usize, usize)], capacity: usize) -> usize {
    let n = items.len();
    let mut dp = vec![vec![0usize; capacity + 1]; n + 1];
    for i in 1..=n {
        let (w, v) = items[i - 1];
        for c in 0..=capacity {
            dp[i][c] = if w <= c {
                dp[i - 1][c].max(v + dp[i - 1][c - w])
            } else {
                dp[i - 1][c]
            };
        }
    }
    dp[n][capacity]
}

Rust (space-optimised rolling array)

pub fn knapsack_rolling(items: &[(usize, usize)], capacity: usize) -> usize {
    let mut dp = vec![0usize; capacity + 1];
    for &(w, v) in items {
        for c in (w..=capacity).rev() {
            dp[c] = dp[c].max(v + dp[c - w]);
        }
    }
    dp[capacity]
}

Type Signatures

Concept	OCaml	Rust
Function signature	`val knapsack : (int * int) list -> int -> int`	`fn knapsack(items: &[(usize, usize)], capacity: usize) -> usize`
Item list	`(int * int) list`	`&[(usize, usize)]` (borrowed slice of tuples)
Memoisation cache	`(int * int, int) Hashtbl.t`	`HashMap<(usize, usize), usize>`
DP table	`int array array` (if bottom-up)	`Vec<Vec<usize>>`

Key Insights

Closure vs free function for mutable cache: In OCaml, let rec solve freely closes

over the mutable Hashtbl. Rust's borrow checker prevents a recursive closure from holding &mut HashMap at the same time as borrowing items; the fix is to lift the helper into a free fn that receives both as parameters.

Tuple destructuring is identical: Both let (w, v) = items.(i) (OCaml) and

let (w, v) = items[i] (Rust) destructure a tuple element from an array/slice — the surface syntax is nearly the same.

**max as method vs free function:** OCaml uses max without with_item (polymorphic

built-in); Rust uses without.max(with_item), a method on the concrete type usize. Both are zero-cost.

Bottom-up avoids stack depth: For large inputs (thousands of items, large capacity)

the recursive top-down approach may overflow the stack. The bottom-up table iterates instead, which is safer and cache-friendlier.

**Rolling array and rev():** The space-optimised variant folds the 2-D table into a

single row by processing capacity in reverse ((w..=capacity).rev()). This ensures that dp[c - w] still reflects the previous item's row — the same invariant the 2-D table maintains explicitly. OCaml would express the same idea with Array.blit or a functional fold over a vector.

When to Use Each Style

Use top-down memoisation when: the problem has sparse subproblem structure (not all (i, cap) pairs are reachable) or you want to stay close to the recursive mathematical definition for readability.

Use bottom-up table when: you need predictable stack usage and every subproblem will be computed regardless — the tight nested loop is also easier to parallelise.

Use rolling array when: memory is the bottleneck and you only need the final answer (not the full DP table for path reconstruction).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust