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

×

Rod cutting dp problem[closed]

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

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2802319
accept rate: 10%

edited 25 Dec '14, 12:59


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.

link

answered 24 Dec '14, 14:15

rvkmr102's gravatar image

4★rvkmr102
713
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★

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<i;j++)
   {
     val[i]= max(val[i], price[j]+ val[i-j-1]);
   }
}
link

answered 28 Dec '14, 00:22

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

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:

×2,032
×633
×5
×4

question asked: 24 Dec '14, 13:41

question was seen: 3,275 times

last updated: 28 Dec '14, 00:22