785 Advanced

785-knapsack-01 — 0/1 Knapsack Problem

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "785-knapsack-01 — 0/1 Knapsack Problem" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. The 0/1 knapsack problem is a foundational combinatorial optimization problem: given items with weights and values and a capacity-limited bag, select items to maximize total value without exceeding capacity. Key difference from OCaml: 1. **Mutability**: Rust's `vec![vec![0; capacity + 1]; n + 1]` with `dp[i][w] = ...` is imperative; OCaml's `for` loop equivalent is similar but uses `Array.set dp.(i).(w) val`.

Tutorial

The Problem

The 0/1 knapsack problem is a foundational combinatorial optimization problem: given items with weights and values and a capacity-limited bag, select items to maximize total value without exceeding capacity. "0/1" means each item is either taken or not (no fractions). It appears in resource allocation, project portfolio selection, cargo loading, and is a building block for more complex optimization problems. The DP solution runs in O(n × W) time, making large instances tractable.

🎯 Learning Outcomes

• Model the 0/1 knapsack as a 2D DP table dp[i][w] = max value using first i items with capacity w

• Implement the recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

• Optimize space from O(n × W) to O(W) using a 1D array with right-to-left iteration

• Understand why right-to-left iteration prevents using the same item twice

• Reconstruct the chosen items by backtracking through the DP table

Code Example

#![allow(clippy::all)]
//! # 0/1 Knapsack Problem
//!
//! Classic dynamic programming problem.

/// Solve 0/1 knapsack problem
pub fn knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();
    let mut dp = vec![vec![0; capacity + 1]; n + 1];

    for i in 1..=n {
        for w in 0..=capacity {
            if weights[i - 1] <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    dp[n][capacity]
}

/// Space-optimized version
pub fn knapsack_optimized(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let mut dp = vec![0; 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]
}

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

    #[test]
    fn test_knapsack() {
        let weights = [1, 2, 3];
        let values = [6, 10, 12];
        assert_eq!(knapsack(&weights, &values, 5), 22);
    }

    #[test]
    fn test_knapsack_optimized() {
        let weights = [1, 2, 3];
        let values = [6, 10, 12];
        assert_eq!(knapsack_optimized(&weights, &values, 5), 22);
    }

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

    #[test]
    fn test_no_capacity() {
        let weights = [1, 2];
        let values = [10, 20];
        assert_eq!(knapsack(&weights, &values, 0), 0);
    }
}

(* 0/1 Knapsack in OCaml — recursive + memoisation + tabulation *)

type item = { weight: int; value: int; name: string }

(* ── Recursive with memoisation ───────────────────────────────────────────────── *)
let solve_memo items capacity =
  let n = Array.length items in
  let memo = Hashtbl.create 64 in
  let rec dp i w =
    if i = n || w = 0 then 0
    else match Hashtbl.find_opt memo (i, w) with
    | Some v -> v
    | None ->
      let item = items.(i) in
      let best =
        if item.weight > w then dp (i+1) w
        else max (dp (i+1) w) (item.value + dp (i+1) (w - item.weight))
      in
      Hashtbl.replace memo (i, w) best;
      best
  in
  dp 0 capacity

(* ── Tabulation ────────────────────────────────────────────────────────────────── *)
let solve_tab items capacity =
  let n = Array.length items in
  (* dp.(i).(w) = max value using first i items with capacity w *)
  let dp = Array.make_matrix (n+1) (capacity+1) 0 in
  for i = 1 to n do
    let item = items.(i-1) in
    for w = 0 to capacity do
      dp.(i).(w) <-
        if item.weight > w then dp.(i-1).(w)
        else max dp.(i-1).(w) (item.value + dp.(i-1).(w - item.weight))
    done
  done;
  (* Traceback *)
  let selected = ref [] in
  let w = ref capacity in
  for i = n downto 1 do
    if dp.(i).(!w) <> dp.(i-1).(!w) then begin
      selected := items.(i-1) :: !selected;
      w := !w - items.(i-1).weight
    end
  done;
  dp.(n).(capacity), !selected

let () =
  let items = [|
    { weight=2; value=6;  name="camera"  };
    { weight=2; value=10; name="laptop"  };
    { weight=3; value=12; name="guitar"  };
    { weight=1; value=4;  name="book"    };
    { weight=4; value=15; name="drone"   };
  |] in
  let capacity = 7 in
  let best_memo = solve_memo items capacity in
  Printf.printf "Memo  best value: %d\n" best_memo;
  let (best_tab, selected) = solve_tab items capacity in
  Printf.printf "Table best value: %d\n" best_tab;
  Printf.printf "Selected items:\n";
  List.iter (fun item ->
    Printf.printf "  %s (w=%d, v=%d)\n" item.name item.weight item.value
  ) selected

Key Differences

Mutability: Rust's vec![vec![0; capacity + 1]; n + 1] with dp[i][w] = ... is imperative; OCaml's for loop equivalent is similar but uses Array.set dp.(i).(w) val.

Space optimization: Both languages implement the 1D right-to-left optimization identically — the algorithm is language-independent.

Reconstruction: Rust backtracks through dp by comparing dp[i][w] with dp[i-1][w]; OCaml uses the same technique.

Bounds checking: Rust's Vec bounds-checks by default; OCaml's Array.unsafe_get skips checks for performance in tight DP loops.

OCaml Approach

OCaml's functional style uses Array.init for DP table construction and Array.fold_left for optimization. The functional approach with Array.init (n+1) (fun i -> Array.init (cap+1) (fun w -> ...)) creates the full table lazily but requires a fix-point or explicit memoization. The imperative style with for loops and Array.set is idiomatic for DP in OCaml despite the functional aesthetic.

Full Source

#![allow(clippy::all)]
//! # 0/1 Knapsack Problem
//!
//! Classic dynamic programming problem.

/// Solve 0/1 knapsack problem
pub fn knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();
    let mut dp = vec![vec![0; capacity + 1]; n + 1];

    for i in 1..=n {
        for w in 0..=capacity {
            if weights[i - 1] <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    dp[n][capacity]
}

/// Space-optimized version
pub fn knapsack_optimized(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let mut dp = vec![0; 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]
}

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

    #[test]
    fn test_knapsack() {
        let weights = [1, 2, 3];
        let values = [6, 10, 12];
        assert_eq!(knapsack(&weights, &values, 5), 22);
    }

    #[test]
    fn test_knapsack_optimized() {
        let weights = [1, 2, 3];
        let values = [6, 10, 12];
        assert_eq!(knapsack_optimized(&weights, &values, 5), 22);
    }

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

    #[test]
    fn test_no_capacity() {
        let weights = [1, 2];
        let values = [10, 20];
        assert_eq!(knapsack(&weights, &values, 0), 0);
    }
}

(* 0/1 Knapsack in OCaml — recursive + memoisation + tabulation *)

type item = { weight: int; value: int; name: string }

(* ── Recursive with memoisation ───────────────────────────────────────────────── *)
let solve_memo items capacity =
  let n = Array.length items in
  let memo = Hashtbl.create 64 in
  let rec dp i w =
    if i = n || w = 0 then 0
    else match Hashtbl.find_opt memo (i, w) with
    | Some v -> v
    | None ->
      let item = items.(i) in
      let best =
        if item.weight > w then dp (i+1) w
        else max (dp (i+1) w) (item.value + dp (i+1) (w - item.weight))
      in
      Hashtbl.replace memo (i, w) best;
      best
  in
  dp 0 capacity

(* ── Tabulation ────────────────────────────────────────────────────────────────── *)
let solve_tab items capacity =
  let n = Array.length items in
  (* dp.(i).(w) = max value using first i items with capacity w *)
  let dp = Array.make_matrix (n+1) (capacity+1) 0 in
  for i = 1 to n do
    let item = items.(i-1) in
    for w = 0 to capacity do
      dp.(i).(w) <-
        if item.weight > w then dp.(i-1).(w)
        else max dp.(i-1).(w) (item.value + dp.(i-1).(w - item.weight))
    done
  done;
  (* Traceback *)
  let selected = ref [] in
  let w = ref capacity in
  for i = n downto 1 do
    if dp.(i).(!w) <> dp.(i-1).(!w) then begin
      selected := items.(i-1) :: !selected;
      w := !w - items.(i-1).weight
    end
  done;
  dp.(n).(capacity), !selected

let () =
  let items = [|
    { weight=2; value=6;  name="camera"  };
    { weight=2; value=10; name="laptop"  };
    { weight=3; value=12; name="guitar"  };
    { weight=1; value=4;  name="book"    };
    { weight=4; value=15; name="drone"   };
  |] in
  let capacity = 7 in
  let best_memo = solve_memo items capacity in
  Printf.printf "Memo  best value: %d\n" best_memo;
  let (best_tab, selected) = solve_tab items capacity in
  Printf.printf "Table best value: %d\n" best_tab;
  Printf.printf "Selected items:\n";
  List.iter (fun item ->
    Printf.printf "  %s (w=%d, v=%d)\n" item.name item.weight item.value
  ) selected

✓ Tests Rust test suite

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

    #[test]
    fn test_knapsack() {
        let weights = [1, 2, 3];
        let values = [6, 10, 12];
        assert_eq!(knapsack(&weights, &values, 5), 22);
    }

    #[test]
    fn test_knapsack_optimized() {
        let weights = [1, 2, 3];
        let values = [6, 10, 12];
        assert_eq!(knapsack_optimized(&weights, &values, 5), 22);
    }

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

    #[test]
    fn test_no_capacity() {
        let weights = [1, 2];
        let values = [10, 20];
        assert_eq!(knapsack(&weights, &values, 0), 0);
    }
}

Deep Comparison

OCaml vs Rust: Knapsack 01

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Add item reconstruction: modify knapsack to also return the indices of the chosen items by backtracking through the DP table.

Implement the unbounded knapsack variant where each item can be taken multiple times, modifying the recurrence and iteration direction.

Write a branch-and-bound solver for knapsack that prunes branches where the remaining capacity cannot improve the best-so-far solution, and compare it against DP for small instances.

Open Source Repos

functional-rust

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

Rust