We are given a rod of length L, our task is to cut the rod into segments of x, y & z such that the total number of cut segments formed are maximized. Note – The cut segments should be of length x, y & z only.
Example –
Input: L = 15, x = 2, y = 35, z = 7
Output: 6
Explanation: rod of length 15 can be divided into
segments of size (2, 2, 2, 2, 2, 5}.
Hence total 6 segments are possible.
Input: L = 9, p = 2, q = 5, r = 4
Output: 2
Explanation: rod of length 9 can be divided into,
2 segments of size {5, 4}.
This problem can be solved using dynamic programming in O(3*N) time. Since we have to find the maximum number of cuts that can be made on the rod of length L, so for the current length we will make the cut of each x, y, and z length and find the maximum number of cuts that can be made on the remaining length + 1. The required answer will be max(L-x, L-y, L-z) + 1 i.e. the maximum number of cut made till now + 1(current cut). This step will require us making cut in length i ranging from 1 to L. A cut will only be possible if i>= (x, y, z).
Hence the recurrence relation for this problem will be –
f(l) = 1 + maximum( f(l-x), f(l-y), f(l-z))
Algorithm
arr[0] = x
arr[1] = y
arr[2] = z
for(int i=0; i<=3; i++)
for(int j=0; j<=n; j++)
if(arr[i-1] <= j)
{
if(arr[i-1] == j)
dp[i][j] = max(1, dp[i-1][j]);
else{
if(dp[i][j-arr[i-1]] == 0)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(1+dp[i][j-arr[i-1]], dp[i-1][j]);
}
}
else
dp[i][j] = dp[i-1][j];
}
}
Implementation of the above Algorithm
// C++ program to maximize the number
// of segments of length x, y and z
#include<bits/stdc++.h>
using namespace std;
//Function to return the maximum number
//of cut segments possible
int maximizeTheCuts(int n, int x, int y, int z)
{
int m=4;
// Array to store the cut at each length n
int dp[m][n+1] = {0};
//create an array consisting of x,y and z
int arr[] = {x,y,z};
//for each element in array i.e. x, y and z
for(int i=0; i<=3; i++)
{
//consider every possible length in range 0 to l
for(int j=0; j<=n; j++)
{
//If the length of rod is 0 or no cut segment
//is available then max number of cuts are 0
if(i==0 || j==0)
dp[i][j] = 0;
//If the current length of rod is
//greater than current segment
else if(arr[i-1] <= j)
{
//if current length is equivalent to current
//segment size then maximum number of cuts
//max of 1 , maxium cut possible without
//current segment
if(arr[i-1] == j)
dp[i][j] = max(1, dp[i-1][j]);
else{
if(dp[i][j-arr[i-1]] == 0)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(1+dp[i][j-arr[i-1]], dp[i-1][j]);
}
}
//If cut at this length is not possible
//copy maxium number of cuts possible at
//this length without the current segment
else
dp[i][j] = dp[i-1][j];
}
}
// return value corresponding to length l
return dp[3][n];
}
//The main Driver Code
int main() {
int l, x, y, z;
l = 15;
x = 2;
y = 5;
z = 7;
cout<<maximizeTheCuts(l,x,y,z)<<endl;
return 0;
}
Output 6
Time complexity
The run time complexity of the above algorithm is O(3*N) ≈ O(N) because we are using a single for loop till length ‘N’ and another loop runs 3 times only, which is constant.