This is a C++ Program that Solves Rod Cutting Problem using Dynamic Programming technique.
Given a rod of size n and values of various sizes of rod. The problem is to cut the rod in such a way that the sum of values of the pieces is maximum.
The problem can be solved by calculating the maximum attainable value of rod by cutting in various pieces in a bottom up fashion by first calculating for smaller value of n and then using these values to calculate higher values of n.
The time complexity of this solution is O(n^2).
Case-1:
n=5 value[]= 2 3 7 8 10 for sizes 1,2,3,4,5 respectively Expected result=11 by cutting the rod in pieces of sizes 1,1 and 3
Case-2:
n=7 value[]= 2 7 8 25 17 28 30 Expected result=34 by cutting the rod in pieces of sizes 1,2 and 4
Here is source code of the C++ Program to Solve Rod Cutting Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<climits>
using namespace std;
int rodCutting(int n, int value[])
{
int i,j;
//we will calculate the maximum attainable value of rod in a bottom up fashion by first calculating for smaller value of n and then using these values to calculate higher values of n
//create an array to store the results
int result[n+1];
//result[i]=maximum attainable value of rod of size i
//initialization
result[0]=0;
//in every iteration, find the result for rod of size i
for(i=1;i<=n;i++)
{
result[i]=INT_MIN;
//try to cut the rod of length i into various values of j and select the one which gives the maximum value
for(j=0;j<i;j++)
{
result[i]=max(result[i],value[j]+result[i-(j+1)]);
}
}
return result[n];
}
int main()
{
int n;
cout<<"Enter the length of the rod"<<endl;
cin>>n;
int value[n];
//value[i]=value of rod of size i+1
//value[0]=value of rod of size 1
//value[1]=value of rod of size 2
cout<<"Enter the values of pieces of rod of all size"<<endl;
for(int i=0;i<n;i++)
cin>>value[i];
cout<<"Maximum obtainable value by cutting up the rod in many pieces are"<<endl;
cout<<rodCutting(n,value);
cout<<endl;
return 0;
}
In the main function, we ask the user to input the length of rod and values of pieces of rod of all size. We pass these values to the function rodCutting as parameters. This function will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ rod_cutting.cpp $ ./a.out Enter the length of the rod Enter the length of the rod 7 Enter the values of pieces of rod of all size 2 7 8 25 17 28 30 Maximum obtainable value by cutting up the rod 34
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
- Practice Programming MCQs
- Check Computer Science Books
- Check Data Structure Books