This is a C++ Program that Solves Rod Cutting Problem using Dynamic Programming technique.
Problem Description
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.
Problem Solution
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).
Expected Input and Output
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
Program/Source Code
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
#include
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
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"<
cout<<"Maximum obtainable value by cutting up the rod in many pieces are"<