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

×

# Rod cutting dp problem[closed]

 1 I went through the explanation on lectures and the code given by geeksforgeeks and I have a little doubt in this line : max_val = max(max_val, price[j] + val[i-j-1]); In this piece of code:  /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ int cutRod(int price[], int n) { int val[n+1]; val[0] = 0; int i, j; // Build the table val[] in bottom up manner and return the last entry // from the table for (i = 1; i<=n; i++) { int max_val = INT_MIN; for (j = 0; j < i; j++) max_val = max(max_val, price[j] + val[i-j-1]); val[i] = max_val; } return val[n]; }  What I understood from the solution was that we take price of one piece and take the best of what else is left. For example : If the length of rod is 4 then we should take max of (Price of not cutting at all,that is taking the rod of 4 as it is to get the maximum revenue, (Price of 1 ,best of 3 || Price of 2,best of 2,etc..)) So according to me the code should be : max_val = max(Price of ith piece,Price[j]+val[i-j-1]) or something like that. asked 24 Dec '14, 13:41 291●2●3●20 accept rate: 10%

 2 Price of not cutting at all is taken care of . Here price[] contains prices of different pieces of length i at index i-1 i.e. price[0]=price of a piece of length 1. Outer loop evaluates val[i] for each i the maximum value for length i. Inner loop evaluates the price we can get on cutting the rod after (j+1) length piece. For example in case i=4 j=0 price of length 1 piece and best of length 3 j=1 price of length 2 piece and best of length 2 j=2 price of length 3 piece and best of length 1 j=3 price of length 4 piece and best of length 0 Last case checks for no cut at all. Confusion may be because of price[] array's indexing. answered 24 Dec '14, 14:15 4★rvkmr102 71●3 accept rate: 66% 1 max_val = max(max_val, price[j] + val[i-j-1]); It is just a good way to write if(max_val < price[j]+val[i-j-1]) max_val=price[j]+val[i-j-1]; because the latter accecces the arrays two times. (24 Dec '14, 14:52) rvkmr1024★
 1 As asked above What I understood from the solution was that we take price of one piece and take the best of what else is left. For example : If the length of rod is 4 then we should take max of (Price of not cutting at all,that is taking the rod of 4 as it is to get the maximum revenue, (Price of 1 ,best of 3 || Price of 2,best of 2,etc..)) Please see in the code above, lets say I have to find solution for length 4. Then subproblems I have is (0,4), (1,3), (2,2), (3,1) i.e. every (i,len-i) pair. After every iteration I am not storing the maximum value in my array but in a variable max_value. That's why the code is written as: max_value= max(max_value,price[j]+ val[i-j-1]); i.e. max_value will hold the maximum of all the subproblems. After the inner loop I am finally assigning this value to val[i]. Putting price[i] is of no significance since that is the solution for the subproblem (0,len). We are concerned with all the subproblems and this one gets covered when j is 0 for every i. However, we may have done like: for(i=1;i<=n;i++) { val[i]=price[i-1]; for(j=1;j
 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:

×2,212
×690
×5
×4

question asked: 24 Dec '14, 13:41

question was seen: 3,338 times

last updated: 28 Dec '14, 00:22