1054 Advanced

1054-knapsack-01 — 0/1 Knapsack

Functional Programming

Tutorial

The Problem

The 0/1 knapsack problem is the quintessential combinatorial optimization problem: given items with weights and values, and a weight capacity, select items to maximize total value without exceeding capacity. Each item can be included at most once (0 or 1 times). It has direct applications in resource allocation, financial portfolio optimization, and load balancing.

The DP solution runs in O(n × capacity) time — pseudo-polynomial because it depends on the numeric value of capacity, not just the number of items.

🎯 Learning Outcomes

• Implement the 0/1 knapsack with a 2D DP table

• Optimize to a 1D rolling array using reverse iteration

• Understand why the reverse iteration is necessary for 0/1 (vs unbounded)

• Implement the top-down memoized variant for comparison

• Reconstruct which items were selected using backtracking over the DP table

Code Example

#![allow(clippy::all)]
// 1054: 0/1 Knapsack — 2D DP Table

use std::collections::HashMap;

// Approach 1: 2D Vec DP
fn knapsack_2d(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
    let n = weights.len();
    let mut dp = vec![vec![0i64; capacity + 1]; n + 1];
    for i in 1..=n {
        for w in 0..=capacity {
            dp[i][w] = dp[i - 1][w];
            if weights[i - 1] <= w {
                dp[i][w] = dp[i][w].max(dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    dp[n][capacity]
}

// Approach 2: 1D rolling array
fn knapsack_1d(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
    let mut dp = vec![0i64; capacity + 1];
    for i in 0..weights.len() {
        for w in (weights[i]..=capacity).rev() {
            dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
        }
    }
    dp[capacity]
}

// Approach 3: Recursive with HashMap memoization
fn knapsack_memo(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
    fn solve(
        i: usize,
        w: usize,
        weights: &[usize],
        values: &[i64],
        cache: &mut HashMap<(usize, usize), i64>,
    ) -> i64 {
        if i == 0 || w == 0 {
            return 0;
        }
        if let Some(&v) = cache.get(&(i, w)) {
            return v;
        }
        let skip = solve(i - 1, w, weights, values, cache);
        let take = if weights[i - 1] <= w {
            solve(i - 1, w - weights[i - 1], weights, values, cache) + values[i - 1]
        } else {
            0
        };
        let result = skip.max(take);
        cache.insert((i, w), result);
        result
    }
    let mut cache = HashMap::new();
    solve(weights.len(), capacity, weights, values, &mut cache)
}

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

    #[test]
    fn test_knapsack_2d() {
        assert_eq!(knapsack_2d(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_2d(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }

    #[test]
    fn test_knapsack_1d() {
        assert_eq!(knapsack_1d(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_1d(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }

    #[test]
    fn test_knapsack_memo() {
        assert_eq!(knapsack_memo(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_memo(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }
}

(* 1054: 0/1 Knapsack — 2D DP Table *)

(* Approach 1: 2D array DP *)
let knapsack_2d weights values capacity =
  let n = Array.length weights in
  let dp = Array.init (n + 1) (fun _ -> Array.make (capacity + 1) 0) in
  for i = 1 to n do
    for w = 0 to capacity do
      dp.(i).(w) <- dp.(i - 1).(w);
      if weights.(i - 1) <= w then
        dp.(i).(w) <- max dp.(i).(w)
          (dp.(i - 1).(w - weights.(i - 1)) + values.(i - 1))
    done
  done;
  dp.(n).(capacity)

(* Approach 2: 1D rolling array optimization *)
let knapsack_1d weights values capacity =
  let n = Array.length weights in
  let dp = Array.make (capacity + 1) 0 in
  for i = 0 to n - 1 do
    for w = capacity downto weights.(i) do
      dp.(w) <- max dp.(w) (dp.(w - weights.(i)) + values.(i))
    done
  done;
  dp.(capacity)

(* Approach 3: Recursive with memoization *)
let knapsack_memo weights values capacity =
  let n = Array.length weights in
  let cache = Hashtbl.create 128 in
  let rec solve i w =
    if i = 0 || w = 0 then 0
    else
      match Hashtbl.find_opt cache (i, w) with
      | Some v -> v
      | None ->
        let skip = solve (i - 1) w in
        let take =
          if weights.(i - 1) <= w then
            solve (i - 1) (w - weights.(i - 1)) + values.(i - 1)
          else 0
        in
        let result = max skip take in
        Hashtbl.add cache (i, w) result;
        result
  in
  solve n capacity

let () =
  let weights = [|2; 3; 4; 5|] in
  let values = [|3; 4; 5; 6|] in
  assert (knapsack_2d weights values 5 = 7);
  assert (knapsack_1d weights values 5 = 7);
  assert (knapsack_memo weights values 5 = 7);

  let w2 = [|1; 2; 3|] in
  let v2 = [|6; 10; 12|] in
  assert (knapsack_2d w2 v2 5 = 22);
  assert (knapsack_1d w2 v2 5 = 22);
  assert (knapsack_memo w2 v2 5 = 22);

  Printf.printf "✓ All tests passed\n"

Key Differences

**downto syntax**: OCaml's for w = capacity downto weights.(i) expresses reverse iteration clearly; Rust uses .rev() on a range.

2D vs 1D: Both languages support both approaches; the 1D is preferred for space efficiency when item reconstruction is not needed.

Index vs slice: OCaml's weights.(i) is direct array access; Rust's weights[i] is equivalent with bounds checking.

Reconstruction: Backtracking over the 2D table to find which items were selected is language-independent — both scan from dp[n][capacity] backward.

OCaml Approach

let knapsack weights values capacity =
  let n = Array.length weights in
  let dp = Array.make (capacity + 1) 0 in
  for i = 0 to n - 1 do
    for w = capacity downto weights.(i) do
      dp.(w) <- max dp.(w) (dp.(w - weights.(i)) + values.(i))
    done
  done;
  dp.(capacity)

The downto keyword makes the reverse iteration clear in OCaml. The structure is identical to Rust's approach.

Full Source

#![allow(clippy::all)]
// 1054: 0/1 Knapsack — 2D DP Table

use std::collections::HashMap;

// Approach 1: 2D Vec DP
fn knapsack_2d(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
    let n = weights.len();
    let mut dp = vec![vec![0i64; capacity + 1]; n + 1];
    for i in 1..=n {
        for w in 0..=capacity {
            dp[i][w] = dp[i - 1][w];
            if weights[i - 1] <= w {
                dp[i][w] = dp[i][w].max(dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    dp[n][capacity]
}

// Approach 2: 1D rolling array
fn knapsack_1d(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
    let mut dp = vec![0i64; capacity + 1];
    for i in 0..weights.len() {
        for w in (weights[i]..=capacity).rev() {
            dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
        }
    }
    dp[capacity]
}

// Approach 3: Recursive with HashMap memoization
fn knapsack_memo(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
    fn solve(
        i: usize,
        w: usize,
        weights: &[usize],
        values: &[i64],
        cache: &mut HashMap<(usize, usize), i64>,
    ) -> i64 {
        if i == 0 || w == 0 {
            return 0;
        }
        if let Some(&v) = cache.get(&(i, w)) {
            return v;
        }
        let skip = solve(i - 1, w, weights, values, cache);
        let take = if weights[i - 1] <= w {
            solve(i - 1, w - weights[i - 1], weights, values, cache) + values[i - 1]
        } else {
            0
        };
        let result = skip.max(take);
        cache.insert((i, w), result);
        result
    }
    let mut cache = HashMap::new();
    solve(weights.len(), capacity, weights, values, &mut cache)
}

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

    #[test]
    fn test_knapsack_2d() {
        assert_eq!(knapsack_2d(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_2d(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }

    #[test]
    fn test_knapsack_1d() {
        assert_eq!(knapsack_1d(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_1d(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }

    #[test]
    fn test_knapsack_memo() {
        assert_eq!(knapsack_memo(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_memo(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }
}

(* 1054: 0/1 Knapsack — 2D DP Table *)

(* Approach 1: 2D array DP *)
let knapsack_2d weights values capacity =
  let n = Array.length weights in
  let dp = Array.init (n + 1) (fun _ -> Array.make (capacity + 1) 0) in
  for i = 1 to n do
    for w = 0 to capacity do
      dp.(i).(w) <- dp.(i - 1).(w);
      if weights.(i - 1) <= w then
        dp.(i).(w) <- max dp.(i).(w)
          (dp.(i - 1).(w - weights.(i - 1)) + values.(i - 1))
    done
  done;
  dp.(n).(capacity)

(* Approach 2: 1D rolling array optimization *)
let knapsack_1d weights values capacity =
  let n = Array.length weights in
  let dp = Array.make (capacity + 1) 0 in
  for i = 0 to n - 1 do
    for w = capacity downto weights.(i) do
      dp.(w) <- max dp.(w) (dp.(w - weights.(i)) + values.(i))
    done
  done;
  dp.(capacity)

(* Approach 3: Recursive with memoization *)
let knapsack_memo weights values capacity =
  let n = Array.length weights in
  let cache = Hashtbl.create 128 in
  let rec solve i w =
    if i = 0 || w = 0 then 0
    else
      match Hashtbl.find_opt cache (i, w) with
      | Some v -> v
      | None ->
        let skip = solve (i - 1) w in
        let take =
          if weights.(i - 1) <= w then
            solve (i - 1) (w - weights.(i - 1)) + values.(i - 1)
          else 0
        in
        let result = max skip take in
        Hashtbl.add cache (i, w) result;
        result
  in
  solve n capacity

let () =
  let weights = [|2; 3; 4; 5|] in
  let values = [|3; 4; 5; 6|] in
  assert (knapsack_2d weights values 5 = 7);
  assert (knapsack_1d weights values 5 = 7);
  assert (knapsack_memo weights values 5 = 7);

  let w2 = [|1; 2; 3|] in
  let v2 = [|6; 10; 12|] in
  assert (knapsack_2d w2 v2 5 = 22);
  assert (knapsack_1d w2 v2 5 = 22);
  assert (knapsack_memo w2 v2 5 = 22);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_knapsack_2d() {
        assert_eq!(knapsack_2d(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_2d(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }

    #[test]
    fn test_knapsack_1d() {
        assert_eq!(knapsack_1d(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_1d(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }

    #[test]
    fn test_knapsack_memo() {
        assert_eq!(knapsack_memo(&[2, 3, 4, 5], &[3, 4, 5, 6], 5), 7);
        assert_eq!(knapsack_memo(&[1, 2, 3], &[6, 10, 12], 5), 22);
    }
}

Deep Comparison

0/1 Knapsack — Comparison

Core Insight

The 0/1 knapsack builds a 2D table where dp[i][w] = max value using first i items with capacity w. The 1D optimization exploits the fact that each row only depends on the previous row, with reverse iteration ensuring items aren't reused.

OCaml Approach

• Array.init for 2D arrays — creates array of arrays

• for w = capacity downto weight for reverse iteration in 1D version

• Hashtbl with tuple keys (i, w) for memoization

• Pattern matching on find_opt for cache access

Rust Approach

• vec![vec![0; cap+1]; n+1] for 2D table

• (weight..=cap).rev() for reverse range — idiomatic Rust

• HashMap<(usize, usize), i64> for memoization with tuple keys

• Nested function with explicit parameter passing (no closure capture of &mut)

Comparison Table

Aspect	OCaml	Rust
2D table	`Array.init (n+1) (fun _ -> Array.make ...)`	`vec![vec![0; cap+1]; n+1]`
Reverse iteration	`for w = cap downto wt`	`(wt..=cap).rev()`
Tuple hash key	`(i, w)` — works directly	`(usize, usize)` — `Hash` auto-derived
Space optimization	1D array with `downto`	1D vec with `.rev()` range
Max function	`max` (built-in)	`.max()` method on `i64`

Exercises

Add item selection reconstruction: return Vec<usize> of selected item indices alongside the maximum value.

Implement the unbounded knapsack (each item can be used multiple times) and compare the recurrence change (no reverse iteration needed).

Solve the fractional knapsack (items can be split) using a greedy algorithm and compare it with the DP solution.

Open Source Repos

functional-rust

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

Rust