Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Maximum Product Cutting Problem.

Objec­tive: Given a rope of length n meters, write an algo­rithm to cut the rope in such a way that prod­uct of dif­fer­ent lengths of rope is max­i­mum. At least one cut has to be made.

Note: Assume that the length of rope is more than 2 meters, since at least one cut has to be made.

This is yet another prob­lem where you will see the advan­tage of dynamic pro­gram­ming over recur­sion. I will show you how by stor­ing and reusing the results of sub-problems will reduce the com­plex­ity of an algo­rithm sig­nif­i­cantly. These kind of ques­tions are asked in interview’s like Ama­zon, Microsoft, Google etc.

Exam­ple:

•	Rope length: 2 
•	Options: (1*1)
•	Maximum Product Cutting : 1*1 = 1

•	Rope length: 3 
•	Options: (1*1*1, 2*1)
•	Maximum Product Cutting : 2*1 = 2

•	Rope length: 4 
•	Options: (1*1*1*1, 2*1*1, 3*1, 2*2)
•	Maximum Product Cutting : 2*2 = 4

•	Rope length: 5 
•	Options: (1*1*1*1*1, 2*1*1*1, 3*1*1, 2*2*1, 3*2)
•	Maximum Product Cutting : 3*2 = 2

Approach:

Using Recur­sion:

This prob­lem is sim­i­lar to “Rod Cut­ting Prob­lem”.

  • Check the prod­ucts of all pos­si­ble cuts can be made in the rope and return the max­i­mum product.
  • Since for every length there are two options, either a cut to be made or not. Solve the prob­lem for both options and choose maximum.
  • After Mak­ing the cut the fur­ther options are , Either this cut will pro­duce the max prod­uct OR we need to make fur­ther cuts

Recur­sive Equation:

Let MPC(n) is the max­i­mum prod­uct for length n.

  • MPC(n) = max(i*(n-i), i*MPC(n-i)) for all (i=1,2.….n) (After Mak­ing the cut the fur­ther options are , Either this cut will pro­duce the max prod­uct OR we need to make fur­ther cuts).

Time Com­plex­ity: O(2n).

Maximum Product Cutting - Recursion

But yet again we are solv­ing many sub prob­lems repeatedly.

Dynamic Pro­gram­ming:

We will solve this prob­lem in Bottom-Up man­ner.

We will store the solu­tions for sub prob­lems when it get­ting solved for the first time and use it again in future so that we don’t have to solve again.

See the Code for bet­ter understanding.

Code:

Output:

Dynamic Programming: Maximum product cutting in 10 is: 36

You may also like...

  • Gau­rav Kumar Arya

    why we use Math.max(j * MPC[i — j], j * (i — j)));
    we can get right answer by using mp=Math.max(mp,j * MPC[i — j]); also

  • Stretch

    what is the time com­plex­ity for this Bot­tom up approach ?