Optimal substructure and dynamic programming for a variant of the rod cutting problem

Question

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise 15ドル.3$-5ドル$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?

Answer 1

Answer My Own Question:

Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i \land L_j \ge 1} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

• Raphael: Another, maybe more elegant way would be to add base cases $R(i, L) = -\infty$ if $\exists j. L[j] < 0$. (For expressing the recurrence; an implementation would proceed as you propose.)
• Raphael: FWIW, the search space is huge compared to the original problem; the resulting algorithm is pseudo-polynomial at best. I wonder if there's not better way to look at the problem. Hm.