1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael Sep 26 '18 at 13:04
  • $\begingroup$ 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. $\endgroup$ – Raphael Sep 26 '18 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.