Rod cutting, told as a paper mill slitting a parent roll
The textbook rod-cutting problem is a winder problem. A parent roll comes off the paper machine at full width; the slitter cuts it into the widths customers ordered; every width has a price. How do you cut one roll for the most revenue? Then: how do you cut a hundred rolls for the least trim?
Same structure as the knapsack post: one instance, each technique animated in the browser, Java at the bottom. Nothing here is a screenshot.
The instance
A parent roll 10 units wide (think 100 inches in 10-inch steps). A slit roll of width w sells for p[w]. The prices aren't linear in width — common widths move at a premium, odd widths sit in the warehouse — which is exactly why the problem is interesting:
1 · Naive recursion
The best revenue for a roll of width n is: pick the first slit i, sell it for p[i], and do the best you can with the n − i that's left. Try every i, keep the max:
r(n) = max over i in 1..n of p[i] + r(n − i), r(0) = 0Correct — and exponential. Watch the call tree for a width-5 roll. Every color is one subproblem; count how many times each one gets recomputed:
r(2) is solved four times, r(1) eight times. For width n the tree has 2ⁿ nodes. A 100-inch roll in one-inch increments would take longer than the mill has been standing. This is the "overlapping subproblems" property, and it's the signal that dynamic programming applies.
2 · Memoization
Same recursion, but write each answer down the first time and look it up after that. The tree collapses — every subproblem is computed once, and the rest of the calls become table lookups:
Top-down with a cache. Each subproblem r(k) is computed once and then does k units of work to combine, so the total is O(n²) instead of O(2ⁿ). This is the version to reach for first when you're converting a recursion: the code barely changes.
3 · Bottom-up
Or drop the recursion entirely. Fill a table from the smallest roll up: to know the best for width k, you only need the answers for widths less than k, and those are already in the table. Watch each cell being decided:
Same O(n²), no call stack, and a second array cut[k] remembers which first slit won at each width. That second array is what turns a number into a plan.
4 · The cut plan
Start at the full roll, take cut[10], move to what's left, repeat. The slitter setup falls out of the table:
Bari's "principle of optimality" in one picture: the best plan for the whole roll is a first cut plus the best plan for the remainder, so if you know the best plan for every smaller width, the whole roll is one lookup. That's the whole idea of DP. Knapsack, matrix chain, LCS, Floyd–Warshall — all the same move with a different sub-problem shape.
What the mill actually faces: cutting stock
Rod cutting is one roll, maximize revenue. The real problem is the reverse: you have orders — so many rolls of each width — and an unlimited supply of 98-inch parent rolls. Minimize the number of parent rolls you consume, which is the same as minimizing trim, the strip at the edge of each roll that nobody ordered and goes back to the pulper.
Each parent roll is cut to a pattern — a combination of order widths that fits in 98. Pick patterns, decide how many times to run each. Here's a small order book and two ways to attack it:
First-fit decreasing sorts the orders by width and packs each into the first roll with room — bin packing, same heuristic as the trailer. Pattern DP does something smarter: for each new roll it solves a small knapsack over the remaining orders to find the pattern with the least trim, runs it, and repeats. It's still greedy across rolls, but each individual roll is optimal, and the trim drops.
The production answer is column generation (Gilmore and Gomory, 1961 — invented for exactly this problem at a paper company). Solve a linear program over the patterns you have; use its dual prices to ask a knapsack "which pattern would help most?"; add it; repeat. The knapsack is the pricing problem. It's the same DP you watched above, now running inside an LP loop. python-cutting-stock-operations-research has the heuristic and the OR-Tools formulation side by side.
The Java
// 1. Naive: O(2^n)
static int naive(int[] p, int n) {
if (n == 0) return 0;
int best = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) best = Math.max(best, p[i] + naive(p, n - i));
return best;
}
// 2. Memoized: O(n^2)
static int memo(int[] p, int n, int[] cache) {
if (n == 0) return 0;
if (cache[n] > 0) return cache[n];
int best = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) best = Math.max(best, p[i] + memo(p, n - i, cache));
return cache[n] = best;
}
// 3. Bottom-up with the plan: O(n^2)
static int[] cut;
static int bottomUp(int[] p, int n) {
int[] r = new int[n + 1];
cut = new int[n + 1];
for (int k = 1; k <= n; k++)
for (int i = 1; i <= k; i++)
if (p[i] + r[k - i] > r[k]) { r[k] = p[i] + r[k - i]; cut[k] = i; }
return r[n];
}
// 4. Recover the slits
static List<Integer> plan(int n) {
List<Integer> slits = new ArrayList<>();
while (n > 0) { slits.add(cut[n]); n -= cut[n]; }
return slits;
}