792 Advanced

792-rod-cutting-dp — Rod Cutting Problem

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "792-rod-cutting-dp — Rod Cutting Problem" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Rod cutting is a classic unbounded knapsack variant: given a rod of length n and prices for each length, maximize revenue by cutting the rod into pieces. Key difference from OCaml: 1. **Recurrence**: Identical to coin change but indexed from 1 (rod lengths) instead of the coin denominations; the algorithms are structurally the same.

Tutorial

The Problem

Rod cutting is a classic unbounded knapsack variant: given a rod of length n and prices for each length, maximize revenue by cutting the rod into pieces. Unlike 0/1 knapsack, pieces of the same length can be used multiple times. It was popularized by Cormen et al. "Introduction to Algorithms" and models real cutting-stock problems in manufacturing, timber processing, and cable management.

🎯 Learning Outcomes

• Model rod cutting as dp[i] = max revenue for rod of length i

• Apply the unbounded knapsack recurrence: for each length i, try all cut positions j from 1 to i

• Understand why this is O(n²) time and O(n) space

• Recognize the connection to the coin change problem (same recurrence structure)

• Reconstruct the optimal cuts taken

Code Example

#![allow(clippy::all)]
//! # Rod Cutting Problem

pub fn rod_cutting(prices: &[usize], n: usize) -> usize {
    let mut dp = vec![0; n + 1];
    for i in 1..=n {
        for j in 1..=i.min(prices.len()) {
            dp[i] = dp[i].max(prices[j - 1] + dp[i - j]);
        }
    }
    dp[n]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_rod() {
        assert_eq!(rod_cutting(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
    }
    #[test]
    fn test_small() {
        assert_eq!(rod_cutting(&[1, 5, 8, 9], 4), 10);
    }
}

(* Rod Cutting — bottom-up DP, unbounded knapsack style *)

let rod_cut prices =
  let n = Array.length prices in
  let dp   = Array.make (n + 1) 0 in
  let cuts = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to i do
      let v = prices.(j - 1) + dp.(i - j) in
      if v > dp.(i) then begin
        dp.(i)   <- v;
        cuts.(i) <- j
      end
    done
  done;
  (* Reconstruct cut sequence *)
  let pieces = ref [] in
  let len    = ref n in
  while !len > 0 do
    pieces := cuts.(!len) :: !pieces;
    len    := !len - cuts.(!len)
  done;
  (dp.(n), List.rev !pieces)

let () =
  (* prices.(i) = price for a rod of length i+1 *)
  let prices = [| 1; 5; 8; 9; 10; 17; 17; 20 |] in
  let (revenue, pieces) = rod_cut prices in
  Printf.printf "Rod length: %d\n" (Array.length prices);
  Printf.printf "Max revenue: %d\n" revenue;
  Printf.printf "Cut into: [%s]\n"
    (String.concat "; " (List.map string_of_int pieces))

Key Differences

Recurrence: Identical to coin change but indexed from 1 (rod lengths) instead of the coin denominations; the algorithms are structurally the same.

Reconstruction: Both use an auxiliary cut array; Rust's Option<usize> per cell is cleaner than OCaml's -1 sentinel.

Manufacturing: Real cutting-stock problems add kerf (saw blade waste) and minimum piece length; both languages model these as additional constraints.

Optimization: The price array may have None (unsaleable lengths); handling this requires wrapping prices in Option.

OCaml Approach

OCaml implements the same recurrence with Array.make (n+1) 0 and nested for loops. The reconstruction uses a cut: int array tracking which cut was made at each length. Functional style can use Array.fold_left over cut lengths. OCaml's List.init generates the price list naturally. The rod cutting problem is typically presented alongside the coin change problem in OCaml algorithm courses.

Full Source

#![allow(clippy::all)]
//! # Rod Cutting Problem

pub fn rod_cutting(prices: &[usize], n: usize) -> usize {
    let mut dp = vec![0; n + 1];
    for i in 1..=n {
        for j in 1..=i.min(prices.len()) {
            dp[i] = dp[i].max(prices[j - 1] + dp[i - j]);
        }
    }
    dp[n]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_rod() {
        assert_eq!(rod_cutting(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
    }
    #[test]
    fn test_small() {
        assert_eq!(rod_cutting(&[1, 5, 8, 9], 4), 10);
    }
}

(* Rod Cutting — bottom-up DP, unbounded knapsack style *)

let rod_cut prices =
  let n = Array.length prices in
  let dp   = Array.make (n + 1) 0 in
  let cuts = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to i do
      let v = prices.(j - 1) + dp.(i - j) in
      if v > dp.(i) then begin
        dp.(i)   <- v;
        cuts.(i) <- j
      end
    done
  done;
  (* Reconstruct cut sequence *)
  let pieces = ref [] in
  let len    = ref n in
  while !len > 0 do
    pieces := cuts.(!len) :: !pieces;
    len    := !len - cuts.(!len)
  done;
  (dp.(n), List.rev !pieces)

let () =
  (* prices.(i) = price for a rod of length i+1 *)
  let prices = [| 1; 5; 8; 9; 10; 17; 17; 20 |] in
  let (revenue, pieces) = rod_cut prices in
  Printf.printf "Rod length: %d\n" (Array.length prices);
  Printf.printf "Max revenue: %d\n" revenue;
  Printf.printf "Cut into: [%s]\n"
    (String.concat "; " (List.map string_of_int pieces))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_rod() {
        assert_eq!(rod_cutting(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
    }
    #[test]
    fn test_small() {
        assert_eq!(rod_cutting(&[1, 5, 8, 9], 4), 10);
    }
}

Deep Comparison

OCaml vs Rust: Rod Cutting Dp

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

Implement rod_cutting_reconstruct(prices, n) -> Vec<usize> that returns the lengths of cuts made (in any order), not just the max revenue.

Add a fixed cost per cut (blade setup cost) to the problem: the revenue for k cuts is max_revenue - k * cut_cost, and find the optimal number of cuts.

Implement the 2D variant: a rectangular sheet can be cut horizontally or vertically, and pieces have prices by (width × height). Model as a 2D DP.

Open Source Repos

functional-rust

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

Rust