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[i] + cutRod(price, ni1));
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\n", cutRod(arr, size));
getchar();
return 0;
}
Resource Link: http://www.geeksforgeeks.org/dynamicprogrammingset13cuttingarod/
Help Please…!!
Thank you…
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[],n1)
(Because you have cut rod of length 1 and remaining rod length is n1)
if you cut rod of length 2 then amount obtained is price[2]+cutRod(int price[],n2)
.
.
.
.
if you cut rod of length 2 then amount obtained is price[n1]+cutRod(int price[],1)
Now you considered all possibilities
So take maximum among them and return it
Hope this answers your question!
1 Like
Lets try to understand the solution using a simple example.Let’s say the given distribution of money for lengths are as:
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[i] + cutRod(price, ni1));
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(401));

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(301));

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.
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
EDIT : Note that the term “1+” only describes the first call i.e i=0,not a generalization as price[i] may vary.
3 Likes
Thanks for that explanation !!
@h1ashdr@gon
what happens after cutrod(p,0) returns 0??i understand why cutrod(p,0) returns 0 but what will happen after that??