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.

1 Like

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.

2 Likes

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.

1 Like

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]);
   }
}
1 Like