You are not logged in. Please login at www.codechef.com to post your questions!

×

# Need help in understanding Recursion in Rod Cutting Probelm

 0 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 #include // 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

 3 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
 1 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! answered 26 Dec '14, 22:29 384●2●6●13 accept rate: 11% thanks.. :) (27 Dec '14, 00:09)
 0 @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?? answered 19 Apr '15, 03:00 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×299
×3

question asked: 26 Dec '14, 21:42

question was seen: 6,030 times

last updated: 19 Apr '15, 03:00