I cannot understand the hint as in the problem no price according to length is given in rod cutting problem

#1

Can you please hep to understand this problem

#2

Hello @manikjindal49 what you have not understood?
Could you please elaborate?

#3

The concept of the problem and how to tackle it and also prices are not given according to each cut of rd in the problem

#4

Please help me and clear my doubts

#5

Hello @manikjindal49 i am sorry for the delay there was some network issue.
it is given in the input format that n is the length of the array and after that in the array you are given with the prices only.

#6

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:

Screenshot_16 (1)
Screenshot_16 (1)982×511 30.6 KB

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.