Maximum Product Cutting using Dynamic Programming

«
»

This is a C++ Program that Solves Rod Cutting – Maximum Product Problem using Dynamic Programming technique.

Problem Description

You are given a rod of integer length. You have to cut the rod in various pieces such that the product of the lengths of all pieces is maximum.

Problem Solution

Calculate the results in bottom up fashion, starting from 1 and cache the results to avoid recomputation.

Expected Input and Output

Case-1:

If length=1, 
Expected result=0 since the rod can not be cut

Case-2:

advertisement
advertisement
If length=2, 
Expected result=1 (1*1)

Case-3:

If length=3, 
Expected result=2 (2*1)
Program/Source Code

Here is source code of the C++ Program to Solve Rod Cutting – Maximum Product Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Participate in Data Structure I Certification Contest of the Month Now!
  1.  
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. int maxProductCutting(int length)
  6. {
  7.     //array to cache results
  8.     int result[length+1];
  9.  
  10.     //result[i]=maximum product after cutting the rod of length i
  11.  
  12.     //initialization
  13.  
  14.     //rod of length 0 and 1 can not be cut into pieced
  15.     result[0]=result[1]=0;
  16.  
  17.     for(int i=2;i<=length;i++)
  18.     {
  19.         result[i]=0;
  20.         for(int j=1;j<=i/2;j++)
  21.         {
  22.             result[i]=max(result[i],max(j*(i-j),j*result[i-j]));
  23.         }
  24.     }
  25.  
  26.     return result[length];
  27. }
  28.  
  29. int main()
  30. {
  31.     int length;
  32.     cout<<"Enter the length of the rod"<<endl;
  33.     cin>>length;
  34.  
  35.     cout<<"Maximum product after cutting the rod into pieces is "<<endl;
  36.     cout<<maxProductCutting(length);
  37.  
  38.     cout<<endl;
  39.     return 0;
  40. }
Program Explanation

In the main function, we ask the user to input the value for length of hte rod. We pass this value to the function maxProductCutting as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

advertisement
Runtime Test Cases
 
Case-1:
$ g++ max_product_cutting.cpp
$ ./a.out
Enter the length of the rod
7
Maximum product after cutting the rod into pieces is 
12

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.