Need help in understanding Recursion in Rod Cutting Probelm

recursion
rod-cutting

#1

I was going through the explanation for Rod Cutting Problem on geeksforgeeks and there this code was mention to solve Rod Cutting Problem but i am weak in recursion and don’t know anything about DP.

And i am unable to visualize what is happening there in this code in recursive part.

So Please can anyone help me out please…!!

Problem Statement:

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

And here is the code:

// A Naive recursive solution for Rod cutting problem
#include<stdio.h>
#include<limits.h>
 
// A utility function to get the maximum of two integers
int max(int a, int b) { return (a > b)? a : b;}
 
/* Returns the best obtainable price for a rod of length n and
   price[] as prices of different pieces */
int cutRod(int price[], int n)
{
   if (n <= 0)
     return 0;
   int max_val = INT_MIN;
 
   // Recursively cut the rod in different pieces and compare different 
   // configurations
   for (int i = 0; i<n; i++)
         max_val = max(max_val, price* + cutRod(price, n-i-1));
 
   return max_val;
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("Maximum Obtainable Value is %d

", cutRod(arr, size));
getchar();
return 0;
}
Resource Link: http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

Help Please…!!

Thank you… :slight_smile:


#2

Here cutRod(int price[],int n) returns maximum amount obtained by cutting up the rod and selling the pieces.

Suppose
if you cut rod of length 1 then amount obtained is price[1]+cutRod(int price[],n-1)

(Because you have cut rod of length 1 and remaining rod length is n-1)

if you cut rod of length 2 then amount obtained is price[2]+cutRod(int price[],n-2)

.

.

.

.

if you cut rod of length 2 then amount obtained is price[n-1]+cutRod(int price[],1)

Now you considered all possibilities

So take maximum among them and return it

Hope this answers your question!


#3

Lets try to understand the solution using a simple example.Let’s say the given distribution of money for lengths are as:
alt text

Let’s consider L=4 for the first sub case.
Since our condition does not match the base condition we enter the for loop.

for (int i = 0; i<n; i++)
     max_val = max(max_val, price* + cutRod(price, n-i-1));

Since we passed n=4, our loop will run 4 times from i=0 to i=3.

  • First execution :

    max_val=max(max_val,price[0]+cutRod(price,3(4-0-1));

  • This will give rise to
    cutRod(price,3)

  • Now our subproblem has been further
    broken down into the best possible
    profit for a length of rod 3.

  • So our 2nd call :

    max_val=max(max_val,price[0]+cutRod(price,2(3-0-1));

  • Similarly after computing till the
    length of the last combination i,e
    1.We will have the values of cutRod(price,1…2…3…4)

Now we compare!

  • Go back to the first execution.
    max_val=max(max_val,price[0]+cutRod(price,4);
    This code basically means the best
    profitable cut of length of rod
    4.There are various combinations possible. (2,2) (3,1) (0,4)…in this
    case we don’t cut at all…One might
    argue that (1,1,2) is also possible
    but remember that since we have
    precomputed all the values then our
    program already knows the best
    combination possible for cutting a
    rod of length 2, so we needn’t worry
    about that :).

  • So it turns out from simple
    observation that :
    cutRod(price,4)=10…taking the
    combination (2,2) you can verify
    this. cutRod(price,3)=8
    cutRod(price,2)=5 cutRod(price,1)=1

Here is a visual representation.
alt text

In case the image doesn’t fit in,here is a direct link (http://discuss.codechef.com/upfiles/Screenshot_16.png)
Hope it helps now :).
Sorry if I went wrong anywhere,feel free to correct me.
My first explanation attempt ever.Cheers :smiley:

EDIT : Note that the term “1+” only describes the first call i.e i=0,not a generalization as price may vary.*


#4

@h1ashdr@gon
what happens after cut-rod(p,0) returns 0??i understand why cut-rod(p,0) returns 0 but what will happen after that??


#5

Thanks for that explanation !! :slight_smile:


#6

thanks… :slight_smile: