Rod Cutting Problem using Dynamic Programming

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<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;
```
```
}
```

Program Explanation

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Runtime Test Cases

 
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.

If you find any mistake above, kindly email to [email protected]

« Prev - Floyd Warshall Algorithm using Dynamic Programming

» Next - Binomial Coefficient using Dynamic Programming

Related Posts:

Practice Computer Science MCQs
Check Programming Books
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs

Recommended Articles: