Dynamic Programming • Unbounded Knapsack

Rod Cutting

Given a rod of length n and an array of prices for all pieces of size smaller than n, find the maximum value obtained by cutting up the rod and selling the pieces.

Try Interactive Simulator

Overview

This is the classic Unbounded Knapsack problem. You have a "knapsack" (rod) of capacity `n`, and you want to fill it with "items" (cuts) that have weight (length) and value (price).

Infinite Supply

Because you can cut multiple pieces of the same length (e.g., cut a rod of length 4 into four pieces of length 1), we iterate the inner loop from LEFT to RIGHT.

The Recurrence

`dp[j]` represents the max profit for a rod of length `j`. To update it, we see if making a cut of `len` improves it: `dp[j - len] + price[len]`.

1D Space Optimization

Because we only need the answers from the current row and the left side of the current row, a single 1D array perfectly captures the state transitions.

Len: 1

$1

Len: 2

$5

Len: 3

$8

Len: 4

$9

DP Array (Max Profit for Rod Length J)

j=0

0

j=1

0

j=2

0

j=3

0

j=4

0

Code Tracker

:::

1let dp = new Array(n + 1).fill(0);

2// Note: length is 1-indexed, so price index is length-1

3for (let len = 1; len <= n; len++) {

4 // Left-to-right traversal means we can use the same length multiple times

5 for (let j = len; j <= n; j++) {

6 dp[j] = Math.max(dp[j], dp[j - len] + prices[len - 1]);

7 }

8}

9return dp[n];