rod cutting Algorithm
The rod cutting algorithm is a classic optimization problem in computer science and operations research, often used to illustrate the power of dynamic programming. It deals with the challenge of cutting a rod of a given length into smaller pieces (integer lengths) so as to maximize the total revenue obtained from selling these pieces. Each piece has a specific price associated with it, and the objective is to find the optimal way to cut the rod in order to maximize the total profit. The problem can be solved using a variety of approaches, including recursive techniques, dynamic programming, and memoization.
Dynamic programming is a particularly effective method for solving the rod cutting problem. This approach involves breaking the problem down into smaller overlapping subproblems and iteratively solving them in a bottom-up manner. The algorithm starts by determining the maximum revenue for rods of length 1, 2, 3, and so on, up to the given length of the rod. At each step of the algorithm, the maximum revenue for a specific rod length is computed by considering all possible ways of cutting the rod and selecting the cut that yields the highest total revenue. The dynamic programming approach ensures that the same subproblems are not solved multiple times, which significantly reduces the overall computational complexity and time required to find the optimal solution. The rod cutting algorithm has many real-world applications, including resource allocation, production planning, and telecommunications network design.
#include<iostream>
#include<climits>
using namespace std;
int rodCutting(int n, int value[])
{
int i,j;
int result[n+1];
result[0]=0;
for(i=1;i<=n;i++)
{
result[i]=INT_MIN;
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];
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;
}
