0
$\begingroup$

In CLRS (Intro to algorithms) on page 362, it says eqn(1) :

eqn 1

can be simplified to this equation(2):

eqn 2

I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal proof but one that makes logical and intuitive sense. (General arguments or assumptions that lead to this simplification are also welcome). Any effort is much appreciated. (Thanks)

Update
I want to know how the second equation is valid if we are not considering the optimal revenues on both sides but only the optimal revenue of the right-hand piece as suggested by the second equation.
I.e. in the second equation, we use the price of the left piece and then add it to the optimal revenue of the right-hand piece.

$\endgroup$
  • $\begingroup$ I think you shouldn't think or the second formula as a consequence of the first (although it is of course, as both equal $r_n$), but simply derive it from scratch. This is actually what is done in the CLRS. The paragraph preceding this formula explains how. Maybe you could be a bit more precise about what part of this paragraph you struggle with, to help us help you. (And include definitions of $p_i$ and $r_i$ to make the question more self-contained) $\endgroup$ – Tassle Oct 10 at 19:52
  • $\begingroup$ @Tassle I want to know how is the second equation valid if we are not considering the optimal revenues on both sides but only the optimal revenue of the right-hand piece as suggested by the second equation. $\endgroup$ – African_king Oct 10 at 20:10
0
$\begingroup$

I feel like this is basically paraphrasing the explantion in CLRS but maybe it will help.

Let $j$ be the length of the leftmost rod piece in an optimal solution. This piece has a cost of $p_j$ and so it contributes exactly that much to the total revenue. It is easy to see that the remaining part of the rod (of length $n-j$) must be divided up in an optimal manner as well for the whole thing to be optimal (and thus leads to a revenue of $r_{n-j}$).

Thus, we have $r_n = p_j +r_{n-j} $. Because $r_n$ is the optimal revenue, $r_n \geq \max_{1\leq i \leq n}\{p_i+r_{n-i}\}$. But we also have $r_n = p_j +r_{n-j} \leq \max_{1\leq i\leq n}\{p_i+r_{n-i}\}$.

Putting both ineqalities together gives $r_n = \max_{1\leq i \leq n}\{p_i+r_{n-i}\}$.

| cite | improve this answer | |
$\endgroup$

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.