1113 Advanced

0/1 Knapsack with Dynamic Programming (Functional Style)

Functional Programming

Tutorial

The Problem

Given items with weights and values and a fixed capacity, find the maximum total value that fits without exceeding the capacity. Each item may be used at most once (0/1 constraint).

🎯 Learning Outcomes

• How space-optimized DP reduces a 2D table to a single row by iterating capacities in reverse

• Using for_each with iterator combinators instead of imperative for loops to express DP transitions functionally

• Why reverse traversal of the capacity dimension is essential for the 0/1 constraint

Code Example

#![allow(clippy::all)]
//! 0/1 Knapsack problem solved with dynamic programming (functional style).

/// Solves the 0/1 Knapsack problem using dynamic programming.
/// Returns the maximum value that can be put in a knapsack of capacity `capacity`.
///
/// # Arguments
/// * `weights` - A slice of item weights.
/// * `values` - A slice of item values (should have same length as `weights`).
/// * `capacity` - The maximum capacity of the knapsack.
///
/// # Example
/// ```
/// use example_1113_knapsack_problem_dynamic_programming_functional::knapsack;
/// let weights = vec![1, 2, 3];
/// let values = vec![10, 15, 40];
/// let capacity = 6;
/// assert_eq!(knapsack(&weights, &values, capacity), 65);
/// ```
pub fn knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();

    // dp table: dp[i][w] is max value using first i items and capacity w
    // Using a single row to optimize space, as dp[i] only depends on dp[i-1]
    let mut dp = vec![0; capacity + 1];

    (0..n).for_each(|i| {
        (0..=capacity).rev().for_each(|w| {
            if weights[i] <= w {
                dp[w] = dp[w].max(values[i] + dp[w - weights[i]]);
            }
        });
    });

    dp[capacity]
}

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

    #[test]
    fn test_knapsack_basic() {
        let weights = vec![1, 2, 3];
        let values = vec![10, 15, 40];
        let capacity = 6;
        assert_eq!(knapsack(&weights, &values, capacity), 65); // Take items 2 (15) and 3 (40) whose weights are 2 and 3 and sum 5, or take items 1 (10) and 3 (40) whose weights are 1 and 3 and sum 4
    }

    #[test]
    fn test_knapsack_no_items() {
        let weights = vec![];
        let values = vec![];
        let capacity = 10;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_zero_capacity() {
        let weights = vec![1, 2, 3];
        let values = vec![10, 15, 40];
        let capacity = 0;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_full_capacity_multiple_items() {
        let weights = vec![2, 3, 4, 5];
        let values = vec![3, 4, 5, 6];
        let capacity = 5;
        assert_eq!(knapsack(&weights, &values, capacity), 7); // Take 2 (3) and 3 (4)
    }

    #[test]
    fn test_knapsack_item_too_heavy() {
        let weights = vec![10];
        let values = vec![100];
        let capacity = 5;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_complex() {
        let weights = vec![3, 4, 6, 5];
        let values = vec![2, 3, 1, 4];
        let capacity = 8;
        assert_eq!(knapsack(&weights, &values, capacity), 6); // Items 3 (weight 6, value 1) + 4 (weight 5, value 4) = cap 11 (too much!) ; it must be items with weight 3 (value 2) and item with weight 5 (value 4)
    }

    #[test]
    fn test_knapsack_duplicate_weights_values() {
        let weights = vec![1, 1, 2];
        let values = vec![10, 15, 20];
        let capacity = 2;
        assert_eq!(knapsack(&weights, &values, capacity), 25); // Take both items of weight 1
    }
}

(* OCaml implementation of the 0/1 Knapsack problem with dynamic programming (functional style) *)

(* Knapsack function: using an array for memoization *)
let knapsack (weights : int array) (values : int array) (capacity : int) : int = 
  let n = Array.length weights in
  let dp = Array.make (capacity + 1) 0 in (* dp[w] = max value for capacity w *)

  for i = 0 to n - 1 do
    (* Iterate backwards to use values from current dp row only, not future values *)
    for w = capacity downto 0 do
      if weights.(i) <= w then
        dp.(w) <- max dp.(w) (values.(i) + dp.(w - weights.(i)))
    done
  done;
  dp.(capacity)

(* Test cases *)
let () = 
  let weights1 = [|1; 2; 3|] in
  let values1 = [|10; 15; 40|] in
  let capacity1 = 6 in
  let result1 = knapsack weights1 values1 capacity1 in
  Printf.printf "Knapsack 1: %d (Expected: 65)\n" result1;
  assert (result1 = 65);

  let weights2 = [||] in
  let values2 = [||] in
  let capacity2 = 10 in
  let result2 = knapsack weights2 values2 capacity2 in
  Printf.printf "Knapsack 2: %d (Expected: 0)\n" result2;
  assert (result2 = 0);

  let weights3 = [|10|] in
  let values3 = [|100|] in
  let capacity3 = 5 in
  let result3 = knapsack weights3 values3 capacity3 in
  Printf.printf "Knapsack 3: %d (Expected: 0)\n" result3;
  assert (result3 = 0);

  let weights4 = [|2; 3; 4; 5|] in
  let values4 = [|3; 4; 5; 6|] in
  let capacity4 = 5 in
  let result4 = knapsack weights4 values4 capacity4 in
  Printf.printf "Knapsack 4: %d (Expected: 7)\n" result4;
  assert (result4 = 7);

  print_endline "All Knapsack tests passed!";

  (* The example from the Rust code: *)
  let weights_rust_ex = [|3; 4; 6; 5|] in
  let values_rust_ex = [|2; 3; 1; 4|] in
  let capacity_rust_ex = 8 in
  let result_rust_ex = knapsack weights_rust_ex values_rust_ex capacity_rust_ex in
  Printf.printf "Rust example values: %d (Expected: 6)\n" result_rust_ex;
  assert (result_rust_ex = 6)

Key Differences

Traversal direction: Rust iterates capacities in reverse (rev()) to enforce the 0/1 constraint in-place; OCaml memoization naturally avoids reuse by indexing a fresh cell (i, w) per item

Space complexity: Rust uses O(capacity) space with a single row; OCaml's 2D table uses O(n × capacity) but makes the subproblem structure explicit

Control flow style: Rust expresses loops as iterator combinators (for_each); OCaml expresses recursion as pattern-matched function calls, both avoiding mutable loop variables

OCaml Approach

The OCaml reference uses a recursive function with a 2D memoization table, pattern matching on the item count and remaining capacity to express the same recurrence as top-down recursive case splits rather than bottom-up iteration.

Full Source

#![allow(clippy::all)]
//! 0/1 Knapsack problem solved with dynamic programming (functional style).

/// Solves the 0/1 Knapsack problem using dynamic programming.
/// Returns the maximum value that can be put in a knapsack of capacity `capacity`.
///
/// # Arguments
/// * `weights` - A slice of item weights.
/// * `values` - A slice of item values (should have same length as `weights`).
/// * `capacity` - The maximum capacity of the knapsack.
///
/// # Example
/// ```
/// use example_1113_knapsack_problem_dynamic_programming_functional::knapsack;
/// let weights = vec![1, 2, 3];
/// let values = vec![10, 15, 40];
/// let capacity = 6;
/// assert_eq!(knapsack(&weights, &values, capacity), 65);
/// ```
pub fn knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();

    // dp table: dp[i][w] is max value using first i items and capacity w
    // Using a single row to optimize space, as dp[i] only depends on dp[i-1]
    let mut dp = vec![0; capacity + 1];

    (0..n).for_each(|i| {
        (0..=capacity).rev().for_each(|w| {
            if weights[i] <= w {
                dp[w] = dp[w].max(values[i] + dp[w - weights[i]]);
            }
        });
    });

    dp[capacity]
}

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

    #[test]
    fn test_knapsack_basic() {
        let weights = vec![1, 2, 3];
        let values = vec![10, 15, 40];
        let capacity = 6;
        assert_eq!(knapsack(&weights, &values, capacity), 65); // Take items 2 (15) and 3 (40) whose weights are 2 and 3 and sum 5, or take items 1 (10) and 3 (40) whose weights are 1 and 3 and sum 4
    }

    #[test]
    fn test_knapsack_no_items() {
        let weights = vec![];
        let values = vec![];
        let capacity = 10;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_zero_capacity() {
        let weights = vec![1, 2, 3];
        let values = vec![10, 15, 40];
        let capacity = 0;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_full_capacity_multiple_items() {
        let weights = vec![2, 3, 4, 5];
        let values = vec![3, 4, 5, 6];
        let capacity = 5;
        assert_eq!(knapsack(&weights, &values, capacity), 7); // Take 2 (3) and 3 (4)
    }

    #[test]
    fn test_knapsack_item_too_heavy() {
        let weights = vec![10];
        let values = vec![100];
        let capacity = 5;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_complex() {
        let weights = vec![3, 4, 6, 5];
        let values = vec![2, 3, 1, 4];
        let capacity = 8;
        assert_eq!(knapsack(&weights, &values, capacity), 6); // Items 3 (weight 6, value 1) + 4 (weight 5, value 4) = cap 11 (too much!) ; it must be items with weight 3 (value 2) and item with weight 5 (value 4)
    }

    #[test]
    fn test_knapsack_duplicate_weights_values() {
        let weights = vec![1, 1, 2];
        let values = vec![10, 15, 20];
        let capacity = 2;
        assert_eq!(knapsack(&weights, &values, capacity), 25); // Take both items of weight 1
    }
}

(* OCaml implementation of the 0/1 Knapsack problem with dynamic programming (functional style) *)

(* Knapsack function: using an array for memoization *)
let knapsack (weights : int array) (values : int array) (capacity : int) : int = 
  let n = Array.length weights in
  let dp = Array.make (capacity + 1) 0 in (* dp[w] = max value for capacity w *)

  for i = 0 to n - 1 do
    (* Iterate backwards to use values from current dp row only, not future values *)
    for w = capacity downto 0 do
      if weights.(i) <= w then
        dp.(w) <- max dp.(w) (values.(i) + dp.(w - weights.(i)))
    done
  done;
  dp.(capacity)

(* Test cases *)
let () = 
  let weights1 = [|1; 2; 3|] in
  let values1 = [|10; 15; 40|] in
  let capacity1 = 6 in
  let result1 = knapsack weights1 values1 capacity1 in
  Printf.printf "Knapsack 1: %d (Expected: 65)\n" result1;
  assert (result1 = 65);

  let weights2 = [||] in
  let values2 = [||] in
  let capacity2 = 10 in
  let result2 = knapsack weights2 values2 capacity2 in
  Printf.printf "Knapsack 2: %d (Expected: 0)\n" result2;
  assert (result2 = 0);

  let weights3 = [|10|] in
  let values3 = [|100|] in
  let capacity3 = 5 in
  let result3 = knapsack weights3 values3 capacity3 in
  Printf.printf "Knapsack 3: %d (Expected: 0)\n" result3;
  assert (result3 = 0);

  let weights4 = [|2; 3; 4; 5|] in
  let values4 = [|3; 4; 5; 6|] in
  let capacity4 = 5 in
  let result4 = knapsack weights4 values4 capacity4 in
  Printf.printf "Knapsack 4: %d (Expected: 7)\n" result4;
  assert (result4 = 7);

  print_endline "All Knapsack tests passed!";

  (* The example from the Rust code: *)
  let weights_rust_ex = [|3; 4; 6; 5|] in
  let values_rust_ex = [|2; 3; 1; 4|] in
  let capacity_rust_ex = 8 in
  let result_rust_ex = knapsack weights_rust_ex values_rust_ex capacity_rust_ex in
  Printf.printf "Rust example values: %d (Expected: 6)\n" result_rust_ex;
  assert (result_rust_ex = 6)

✓ Tests Rust test suite

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

    #[test]
    fn test_knapsack_basic() {
        let weights = vec![1, 2, 3];
        let values = vec![10, 15, 40];
        let capacity = 6;
        assert_eq!(knapsack(&weights, &values, capacity), 65); // Take items 2 (15) and 3 (40) whose weights are 2 and 3 and sum 5, or take items 1 (10) and 3 (40) whose weights are 1 and 3 and sum 4
    }

    #[test]
    fn test_knapsack_no_items() {
        let weights = vec![];
        let values = vec![];
        let capacity = 10;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_zero_capacity() {
        let weights = vec![1, 2, 3];
        let values = vec![10, 15, 40];
        let capacity = 0;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_full_capacity_multiple_items() {
        let weights = vec![2, 3, 4, 5];
        let values = vec![3, 4, 5, 6];
        let capacity = 5;
        assert_eq!(knapsack(&weights, &values, capacity), 7); // Take 2 (3) and 3 (4)
    }

    #[test]
    fn test_knapsack_item_too_heavy() {
        let weights = vec![10];
        let values = vec![100];
        let capacity = 5;
        assert_eq!(knapsack(&weights, &values, capacity), 0);
    }

    #[test]
    fn test_knapsack_complex() {
        let weights = vec![3, 4, 6, 5];
        let values = vec![2, 3, 1, 4];
        let capacity = 8;
        assert_eq!(knapsack(&weights, &values, capacity), 6); // Items 3 (weight 6, value 1) + 4 (weight 5, value 4) = cap 11 (too much!) ; it must be items with weight 3 (value 2) and item with weight 5 (value 4)
    }

    #[test]
    fn test_knapsack_duplicate_weights_values() {
        let weights = vec![1, 1, 2];
        let values = vec![10, 15, 20];
        let capacity = 2;
        assert_eq!(knapsack(&weights, &values, capacity), 25); // Take both items of weight 1
    }
}

Exercises

Modify the Rust implementation to also return the list of selected item indices, not just the maximum value

Change the inner loop from rev() to forward order and observe how the result changes — explain why this breaks the 0/1 constraint

Implement an unbounded knapsack variant (each item may be used multiple times) and identify the single traversal-direction change required

Open Source Repos

functional-rust

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

Rust