As per the book "Introduction to Algorithms" , to solve the rod cutting problem for a given length n, we basically iterate over all possible lengths of the first part , and calculate the optimal profit for the remaining part ( either through recursion or via stored values in array ). The profit for the first part is picked directly from the given profit array i.e. the length of the first part is taken to be as it is and not divided. Shouldn't we also consider the optimal cost for the first part ? Isn't the idea of making one part indivisble wrong ?

  • 2
    $\begingroup$ Presumably the book includes a correctness proof. Have you read it? It should convince you that the algorithm is correct. $\endgroup$ – Yuval Filmus Sep 5 '17 at 17:16
  • $\begingroup$ No , it does not explain about the correctness of this approach.If you want , you can verify . It is on page 362, chapter 15 (Dynamic Programming). Book is Introduction To Algorithms ('CLRS') edition 3. $\endgroup$ – Ahmad Naseem Sep 5 '17 at 17:24
  • 1
    $\begingroup$ Assuming you're referring to section 15.1 in CLRS 3rd ed (you need to give a better reference!), that's wrong. The section starts with a length derivation of the recurrence. Read it. $\endgroup$ – Raphael Sep 5 '17 at 17:28
  • 2
    $\begingroup$ In short: Every solution, including optimal ones, have to have a first piece. We optimize over the combination of costs for the first piece and the recursively found optimal solution for the rest, so we're good. That's the basic principle of every inductive/recursive algorithm. $\endgroup$ – Raphael Sep 5 '17 at 17:29
  • $\begingroup$ Which edition do you have ? Mine doesn't say anything like that .The derivation at the beginning is for the approach where we consider optimal profits for both parts and not just for the second one . Can you please further explain your point . I cannot understand it fully? $\endgroup$ – Ahmad Naseem Sep 5 '17 at 17:34

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.