Rod Cutting Problem

The problem

Implement `rodCuttingProblem(lengths, prices, rodLength)`: given a rod of length `rodLength` and a price for each cut length, return the maximum revenue obtainable by cutting it into pieces. There's no limit on how many pieces of any given length you cut, and cuts are free.

`lengths = [1, 2, 3, 4, 5, 6, 7, 8], prices = [1, 5, 8, 9, 10, 17, 17, 20], rodLength = 8` returns `22` — two pieces of length `6` and `2` at `17 + 5`, which beats selling the uncut rod at `20`.

The textbook version gives you only the price array and leaves `lengths` implicit as `[1, 2, …, n]`. Passing it explicitly costs one array and buys the general case where only some lengths are sellable.

The approach

The mapping is total and there's no cleverness underneath it. A cut length is an item, its price is the item's value, its length is the item's weight, and the rod is the bag. The reason it's unbounded and not 0/1 is stated directly in the problem — nothing stops you cutting three pieces of length two — so the include branch has to leave the piece available, which is exactly the same-row lookup from the previous entry.

One difference from the knapsack framing is worth naming: the rod is fully consumed, and the knapsack's bag doesn't have to be. That turns out not to matter, because when `lengths` contains `1` every capacity is exactly fillable and the maximum never leaves slack it could have sold. Drop `1` from the input and the two problems separate — the table still returns the best achievable revenue for a rod you're allowed to leave a stub of, which is the right answer to the general question but not to the strict 'cut it all up' one.

Because the reduction is total, everything from the base unbounded entry carries over untouched: the two zero-seeded loops, the `lengths[i-1] <= j` fits-or-doesn't guard, the `i` versus `i-1` split between the include and exclude branches, and the `O(n * rodLength)` bill. There is genuinely nothing to add — which is the point of solving the general form first.

The classic recursive statement of rod cutting looks different enough to hide this. `revenue(n) = max over i of price[i] + revenue(n - i)` is a 1D recurrence over one parameter, and it's the space-optimised unbounded knapsack with the item dimension already collapsed. Both are correct; the 2D version is easier to derive and the 1D version is what you'd ship. Recognising they're the same table stops you learning rod cutting as its own thing.

The solution

export function rodCuttingProblem(lengths, prices, rodLength) {
  return unboundedKanpsack(lengths, prices, rodLength);
}

function unboundedKanpsack(weights, values, capacity) {
  const memo = Array.from({ length: weights.length + 1 }, () =>
    Array(capacity + 1).fill(null),
  );

  // initialize the first row with 0
  for (let i = 0; i <= weights.length; i++) {
    memo[i][0] = 0;
  }
  // initialize the first column with 0
  for (let j = 0; j <= capacity; j++) {
    memo[0][j] = 0;
  }

  // fill the memo table
  for (let i = 1; i <= weights.length; i++) {
    for (let j = 1; j <= capacity; j++) {
      if (weights[i - 1] <= j) {
        memo[i][j] = Math.max(
          values[i - 1] + memo[i][j - weights[i - 1]],
          memo[i - 1][j],
        );
      } else {
        memo[i][j] = memo[i - 1][j];
      }
    }
  }

  // return the maximum value
  return memo[weights.length][capacity];
}

Time O(n * rodLength)Space O(n * rodLength)