0
$\begingroup$

While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is :

𝑟𝑗=max{𝑝𝑛,𝑟1+𝑟𝑘−1,𝑟2+𝑟𝑗−2,...,𝑟𝑗−1+𝑟1}

In overhead approach, after the initial cut, each sub part of the rod is being considered as an independent problem statement, which makes sense as we don't know which will give the optimal solution. But the turnaround happens after 15.1 is transformed to 15.2 which is :

𝑟𝑛=max1≤𝑖≤𝑛{𝑝𝑖+𝑟𝑛−𝑖}

After the first cut lets take one case of (p3+r4) Since r4 will return the max revenue after further cuts(if required), the first part i.e. p3 of length 3 is not being touched here. What if that length of 3 would yield maximum revenue from cutting it to length 2 and 1 ?

I hope to find an explanantion here. PS: Please excuse the equations syntax. I am not well versed with MathJax and too keen to find answer to this. Cheers!

$\endgroup$
  • $\begingroup$ CLRS (Cormen, Leiserson, Rivest and Stein) is a TERRIBLE book. If you thumb through it, it looks like a rigorous mathematical treatment. However, if you actually spend some time evaluating what they've written, you'll discover that alot of their math is just plain wrong. Those authors are absolute masters at dressing up their sloppy work to make it look impressive. That book is almost nothing but bluster. I have half a mind to write my own book covering the same material. A good proof seeks to make something easier to understand, not make things as sophisticated looking as possible. $\endgroup$ – Toothpick Anemone Aug 16 at 13:49

Your Answer

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

Browse other questions tagged or ask your own question.