1
$\begingroup$

I'm trying to use Mathematica 10.0. to solve a rod cutting problem with naive recursion. The problem is taken from Introduction to Algorithm, 3rd edition.

The length price for rod is defined in the book as

price = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30}

where the i-th element means length i can be sold for price[[i]]. I want to find the optimal cut for given length to generate maximum profit.

Following the idea of naive recursion given in the book, I write following code:

rodcut[price_, length_] := 
  Module[{n = length, q = 0}, 
  If[n == 0, 
    0, 
    For[i = 1, i <= n, i++, 
      q = Max[q, price[[i]] + rodcut[price, n - i]]]; 
      Return[q]]]

However, when I run the code rodcut[price, k], it always output outcome price[[k]]. It seems like the iteration skips the process and just run the last step i = k.

Could anyone give me some help?

$\endgroup$
  • 1
    $\begingroup$ It looks like it's because i gets reset to 1 repeatedly, presumably because it has global scope, simply add i to the list of symbols being declared locally at the top of your Module. $\endgroup$ – Quantum_Oli Nov 11 '16 at 8:45
  • $\begingroup$ Or use Do instead of For. $\endgroup$ – Simon Woods Nov 11 '16 at 19:50
  • $\begingroup$ @Quantum_Oli You're right. i is global variable but I'm wondering how i gets to reset to 1 repeatly $\endgroup$ – nwdsl Nov 12 '16 at 0: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.