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

×

Need help in understanding Recursion in Rod Cutting Probelm

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, 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\n", cutRod(arr, size));
    getchar();
    return 0;
}

Resource Link: http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

Help Please..!!
Thank you.. :)

asked 26 Dec '14, 21:42

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11141
accept rate: 14%

edited 26 Dec '14, 21:45


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[i] + 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 :D

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

link

answered 26 Dec '14, 22:40

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2802319
accept rate: 10%

edited 26 Dec '14, 22:48

Thanks for that explanation !! :)

(27 Dec '14, 00:09) rishabhprsd72★

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!

link

answered 26 Dec '14, 22:29

sainath_b's gravatar image

3★sainath_b
3842613
accept rate: 11%

edited 26 Dec '14, 22:36

thanks.. :)

(27 Dec '14, 00:09) rishabhprsd72★

@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??

link

answered 19 Apr '15, 03:00

rishabh9511's gravatar image

2★rishabh9511
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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