Cutting a Rod problem in C++

In this tutorial, we will learn about cutting a rod problem in C++. We will also see the use of dynamic programming to solve the cutting of the rod problem.

We will also see examples to understand the concept in a better way.

Cutting Rod Problem using Dynamic Programming in C++

In cutting rod problem,

We have given a rod of length n and an array of prices of the length of pieces whose size is smaller than n. We need to determine the maximum price to cut the rod.

Let,s see the example,

length of rod is given 4.
length of pieces---1 2 3 4
prices of pieces---2 5 7 8

maximum prices will be 10.
size of pieces will be 2,2.

In the above example, we can understand the cutting rod problem.

To solve the problem we take the temporary array to obtain the maximum price.

int dp[n+1]

Let,s see the pseudocode,

int max_value use to store the maximum cost.
dp[n] will be the solution.
initialise the dp[0]=0;
i=1;
while i<n+1 do 
   int max_value=INT_MIN.
   j=0.
   while j<i do
      max_value = max(max_value, price[j] + dp[i-j-1]); 
   dp[i] = max_value;
dp[n]is maximum price to cut a rod

Let,s see the value of an array dp for the above example,

length-0 1 2 3  4
cost---0 2 5 7 10

So, for each entry, we need to apply step,

max_value = max(max_value, price[j] + dp[i-j-1]); 
i.e if we select the length j so we need to take the maximum value of
    max_value and cost of j length + maximum cost of i-j length

Now, let’s see the code.

Code implementation in C++ | Cutting a Rod

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
  int price[] = {2,5,7,8}; 
    int n = sizeof(price)/sizeof(price[0]); 
    int dp[n+1]; //store the maximum price of length i
    dp[0] = 0;  
    for (int i = 1; i<=n; i++) 
    { 
       int max_val = INT_MIN; 
       for (int j = 0; j < i; j++) 
         max_val = max(max_val, price[j] + dp[i-j-1]); 
       dp[i] = max_val; 
    } 
    cout<<"Maximum price of rod is:"<<" ";
    cout<<dp[n]<<endl;
}

Output

Maximum price of rod is: 10

You may also learn,

Activity Selection Problem using Greedy method in C++

Program to find all distinct solutions to N-Queens problem in Java

Leave a Reply

Your email address will not be published. Required fields are marked *