This is a C++ Program that Solves Rod Cutting – Maximum Product Problem using Dynamic Programming technique.
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.
Calculate the results in bottom up fashion, starting from 1 and cache the results to avoid recomputation.
Case-1:
If length=1, Expected result=0 since the rod can not be cut
Case-2:
If length=2, Expected result=1 (1*1)
Case-3:
If length=3, Expected result=2 (2*1)
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.
#include<iostream>
using namespace std;
int maxProductCutting(int length)
{
//array to cache results
int result[length+1];
//result[i]=maximum product after cutting the rod of length i
//initialization
//rod of length 0 and 1 can not be cut into pieced
result[0]=result[1]=0;
for(int i=2;i<=length;i++)
{
result[i]=0;
for(int j=1;j<=i/2;j++)
{
result[i]=max(result[i],max(j*(i-j),j*result[i-j]));
}
}
return result[length];
}
int main()
{
int length;
cout<<"Enter the length of the rod"<<endl;
cin>>length;
cout<<"Maximum product after cutting the rod into pieces is "<<endl;
cout<<maxProductCutting(length);
cout<<endl;
return 0;
}
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.
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.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Programming Books
- Apply for Computer Science Internship
- Apply for Data Structure Internship
- Practice Design & Analysis of Algorithms MCQ
- Buy Computer Science Books