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

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?

## 1 Answer

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.

• 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
Sep 26 '18 at 13:04
• 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.
– Raphael
Sep 26 '18 at 13:05