Pattern visualizer
Rod Cutting Problem
Look at any optimal way to cut the rod and ask: what is the FIRST piece cut off? It has some length i, sold for prices[i-1], and whatever is left is a rod of length len-i that must itself be cut optimally — that's the same problem, smaller. Trying every possible first-cut length and keeping the best gives dp[len] = max over cut of prices[cut-1] + dp[len-cut]. Because a length can be reused as many times as it helps (an unbounded supply of cuts), this is unbounded knapsack with piece lengths as weights and prices as values. Animated on: n = 8, prices = [1,5,8,9,10,17,17,20] — cut a rod of length n into pieces and sell each piece at prices[len-1] to maximize total revenue..
dp[len] = max over every first cut of price(cut) + dp[len - cut]
dp over rod length — dp[len] = best revenue cutting a rod of that length
dp[0] = 0: a rod of length 0 has nothing to sell, so it earns nothing. Every longer rod's answer is built out of this.
1FUNCTION rodCut(n, prices):2 dp[0] <- 03 FOR len FROM 1 TO n:4 dp[len] <- -INFINITY5 FOR cut FROM 1 TO len:6 dp[len] <- MAX(dp[len], prices[cut-1] + dp[len-cut])7 RETURN dp[n]
← / → step · space play · Home restart