CODEWITHSUNDEEP
algorithmdynamic-programming
Ahmad Naseem
Ahmad Naseem

Reputation: 104

Alternative approach for Rod Cutting Algorithm ( Recursive )

In the book Introduction To Algorithms , the naive approach to solving rod cutting problem can be described by the following recurrence:

Let q be the maximum price that can be obtained from a rod of length n.

Let array price[1..n] store the given prices . price[i] is the given price for a rod of length i.

rodCut(int n)
{
    initialize q as q=INT_MIN

    for i=1 to n
        q=max(q,price[i]+rodCut(n-i))

    return q
}

What if I solve it using the below approach:

rodCutv2(int n)
{
   if(n==0)
     return 0

    initialize q = price[n]

    for i = 1 to n/2
        q = max(q, rodCutv2(i) + rodCutv2(n-i))

    return q
}

Is this approach correct? If yes, why do we generally use the first one? Why is it better?

NOTE: I am just concerned with the approach to solving this problem . I know that this problem exhibits optimal substructure and overlapping subproblems and can be solved efficiently using dynamic programming.

Upvotes: 1

Views: 569

Answers (3)

Vipul Vikram
Vipul Vikram

Reputation: 33

your 2nd approach is absolutely correct and its time complexity is also same as the 1st one. In Dynamic Programming also, we can make tabulation on same approach.Here is my solution for recursion :

int rodCut (int price[],int n){
      if(n<=0) return 0;
      int ans = price[n-1];
      for(int i=1; i<=n/2 ; ++i){
      ans=max(ans, (rodCut(price , i) + rodCut(price , n-i)));
      }
  return ans;
}

And, Solution for Dynamic Programming :

int rodCut(int *price,int n){
   int ans[n+1];
   ans[0]=0;   // if length of rod is zero
   for(int i=1;i<=n;++i){
       int max_value=price[i-1];
    for(int j=1;j<=i/2;++j){
        max_value=max(max_value,ans[j]+ans[i-j]);
    }
     ans[i]=max_value;
   }
   return ans[n];
}

Upvotes: 0

Aishwarya Verghese
Aishwarya Verghese

Reputation: 26

The problem with the second version is it's not making use of the price array. There is no base case of the recursion so it'll never stop. Even if you add a condition to return price[i] when n == 1 it'll always return the result of cutting the rod into pieces of size 1.

Upvotes: 0

hnefatl
hnefatl

Reputation: 6037

Your algorithm looks almost correct - you need to be a bit careful when n is odd.

However, it's also exponential in time complexity - you make two recursive calls in each call to rodCutv2. The first algorithm uses memoisation (the price array), so avoids computing the same thing multiple times, and so is faster (it's polynomial-time).

Edit: Actually, the first algorithm isn't correct! It never stores values in prices, but I suspect that's just a typo and not intentional.

Upvotes: -1

Related Questions