0/1 Knapsack Solved with Memoized Recursion

Functional Programming

Tutorial

The Problem

The 0/1 knapsack problem asks: given a set of items each with a weight and value, and a knapsack of fixed capacity, which items maximize total value without exceeding the weight limit? Each item is either taken (1) or left (0) — no fractional amounts. The naive recursive solution is exponential (2ⁿ subsets), but memoization reduces it to O(n × W) by caching overlapping subproblems — a canonical example of dynamic programming via top-down recursion.

🎯 Learning Outcomes

• Understand why the knapsack problem has optimal substructure and overlapping subproblems

• Learn how memoization transforms exponential recursion into polynomial time

• See how Rust's HashMap serves as a memo table for recursive DP

• Understand the difference between top-down (memoized recursion) and bottom-up (tabulation) DP

Code Example

#![allow(clippy::all)]
// placeholder

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)

Key Differences

Mutable state threading: Rust requires &mut HashMap as an explicit parameter; OCaml closures capture mutable Hashtbl by reference implicitly.

Recursion style: Both use let rec / recursive functions, but Rust lacks TCO, so deep recursion on very large inputs risks stack overflow.

Cache key: Both use (item_index, capacity) tuples; Rust's HashMap requires Hash + Eq on keys — tuples derive both automatically.

Overflow safety: Rust uses u64 with explicit bounds; OCaml uses arbitrary-precision integers via Zarith for large instances.

OCaml Approach

OCaml uses a Hashtbl for memoization, typically wrapped in a let memo = Hashtbl.create 16 at the top of the function. The recursive function is defined with let rec solve i w = match Hashtbl.find_opt memo (i, w) with Some v -> v | None -> .... OCaml's closures naturally capture the memo table without threading it as a parameter, making the code more concise.

Full Source

#![allow(clippy::all)]
// placeholder

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)

Deep Comparison

Exercises

Implement the base memoized solution and verify it produces the same answer as the brute-force exponential version on small inputs.

Add item reconstruction: trace back through the memo table to identify which items were selected.

Compare performance against bottom-up tabulation (fill a 2D array row by row) on a 100-item, capacity-1000 instance.

Open Source Repos

functional-rust

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

Rust