Maximise number of cuts in a rod if it can be cut only in given 3 sizes

Given a rod of length

N

meters, and the rod can be cut in only 3 sizes

A

,

B

and

C

. The task is to maximizes the number of cuts in rod. If it is impossible to make cut then print

-1

.

Examples:

Input: N = 17, A = 10, B = 11, C = 3 Output: 3 Explanation: The maximum cut can be obtain after making 2 cut of length 3 and one cut of length 11. Input: N = 10, A = 9, B = 7, C = 11 Output: -1 Explanation: It is impossible to make any cut so output will be -1.

Naive Approach:

• Let us assume x, y, and z numbers of rods of sizes A, B, and C respectively are cut. And this can be written as a linear equation: x*A + y*B + z*C = N
• Now, simply iterate over all possible value of x and y and compute z using (N – x*A + y*B) / c.
• If x*A + y*B + z*C = N, then it is one of the possible answers.
• Finally compute the maximum value of x + y + z.

Time Complexity:

O(N

²

)

Auxiliary Space:

O(1)

Efficient Approach:

The problem can be solve using Dynamic Programming.

1. Create a dp[] array of size N and initialise all value to INT_MIN.
2. Set dp[0] = 0, as it will be base case for our approach.
3. Iterate from 1 to N and check if it is possible to make a cut of any of possible length i.e A, B and C, and update dp[i] to minimum of all.

4. dp[i] = min (dp[i], 1 + subresult) where, subresult = min(dp[i – A], min(dp[i – B], dp[i – C]))

5. 1. Here is the implementation of the above approach:

   2. C++

      
      

      
      
      

      // A Dynamic Programming solution for // Maximum Rod cutting problem   #include <bits/stdc++.h> using namespace std;   // function that eturns the maximum // number of rods that can be // made from the rod of length N int cuttingRod(int arr[], int N) {     int dp[N + 1];       // Initializing the number of rods we     // can make from length 0     dp[0] = 0;       // Iterating over lengths that can     // be formed     for (int i = 1; i <= N; i++) {           // Initializing the possible         // cuts as infinite         dp[i] = INT_MIN;           // Cutting the desired lengths         for (int j = 0; j < 3; j++) {               // Checking whether the length of             // rod becomes 0 or if after cutting             // the rod, it becomes useless             if ((i - arr[j]) >= 0                 && dp[i - arr[j]] != INT_MIN) {                   // Choosing the maximum                 // possible desired                 // length cuts to be made                 dp[i] = max(dp[i - arr[j]] + 1,                             dp[i]);             }         }     }     return dp[N]; }   // Driver code int main() {     int N = 17;     int arr[] = { 10, 11, 3 };     cout << cuttingRod(arr, N);     return 0; }

      Java

      
      

      
      
      

      // A Dynamic Programming solution for // Maximum Rod cutting problem class GFG{   // Function that eturns the maximum // number of rods that can be // made from the rod of length N static int cuttingRod(int arr[], int N) {     int []dp = new int[N + 1];       // Initializing the number of rods we     // can make from length 0     dp[0] = 0;       // Iterating over lengths that can     // be formed     for(int i = 1; i <= N; i++)     {                   // Initializing the possible         // cuts as infinite         dp[i] = Integer.MIN_VALUE;           // Cutting the desired lengths         for(int j = 0; j < 3; j++)         {                           // Checking whether the length of             // rod becomes 0 or if after cutting             // the rod, it becomes useless             if ((i - arr[j]) >= 0 &&               dp[i - arr[j]] != Integer.MIN_VALUE)             {                                   // Choosing the maximum                 // possible desired                 // length cuts to be made                 dp[i] = Math.max(dp[i - arr[j]] + 1,                                  dp[i]);             }         }     }     return dp[N]; }   // Driver code public static void main(String[] args) {     int N = 17;     int arr[] = { 10, 11, 3 };           System.out.print(cuttingRod(arr, N)); } }   // This code is contributed by Princi Singh

      Python3

      
      

      
      
      

      # A Dynamic Programming solution for # Maximum Rod cutting problem import sys   # Function that returns the maximum # number of rods that can be # made from the rod of length N def cuttingRod(arr, N):       dp = (N + 1) * [0]       # Initializing the number of rods we     # can make from length 0     dp[0] = 0       # Iterating over lengths that can     # be formed     for i in range (1, N + 1):           # Initializing the possible         # cuts as infinite         dp[i] = -sys.maxsize - 1           # Cutting the desired lengths         for j in range(3):               # Checking whether the length of             # rod becomes 0 or if after cutting             # the rod, it becomes useless             if ((i - arr[j]) >= 0 and               dp[i - arr[j]] != -sys.maxsize-1):                   # Choosing the maximum                 # possible desired                 # length cuts to be made                 dp[i] = max(dp[i - arr[j]] + 1,                             dp[i])     return dp[N]   # Driver code if __name__ == "__main__":       N = 17     arr = [ 10, 11, 3 ]           print(cuttingRod(arr, N))   # This code is contributed by chitranayal

      C#

      
      

      
      
      

      // A Dynamic Programming solution for // Maximum Rod cutting problem using System;   class GFG{   // Function that eturns the maximum // number of rods that can be // made from the rod of length N static int cuttingRod(int[] arr, int N) {     int []dp = new int[N + 1];       // Initializing the number of rods we     // can make from length 0     dp[0] = 0;       // Iterating over lengths that can     // be formed     for(int i = 1; i <= N; i++)     {                   // Initializing the possible         // cuts as infinite         dp[i] = Int32.MinValue;           // Cutting the desired lengths         for(int j = 0; j < 3; j++)         {                           // Checking whether the length of             // rod becomes 0 or if after cutting             // the rod, it becomes useless             if ((i - arr[j]) >= 0 &&               dp[i - arr[j]] != Int32.MinValue)             {                                   // Choosing the maximum                 // possible desired                 // length cuts to be made                 dp[i] = Math.Max(dp[i - arr[j]] + 1,                                  dp[i]);             }         }     }     return dp[N]; }   // Driver code public static void Main() {     int N = 17;     int[] arr = { 10, 11, 3 };           Console.Write(cuttingRod(arr, N)); } }   // This code is contributed by code_hunt

      Javascript

      
      

      
      
      

      // A Dynamic Programming solution for // Maximum Rod cutting problem   // function that eturns the maximum // number of rods that can be // made from the rod of length N const cuttingRod = (arr, N) => {     const dp = new Array(N + 1);           // Initializing the number of rods we     // can make from length 0     dp[0] = 0;           // Iterating over lengths that can     // be formed     for (let i = 1; i <= N; i++) {                   // Initializing the possible         // cuts as infinite         dp[i] = Number.MIN_SAFE_INTEGER;                    // Cutting the desired lengths         for (let j = 0; j < 3; j++) {                            // Checking whether the length of             // rod becomes 0 or if after cutting             // the rod, it becomes useless             if ((i - arr[j]) >= 0 && dp[i - arr[j]] !== Number.MIN_SAFE_INTEGER) {                                   // Choosing the maximum                 // possible desired                 // length cuts to be made                 dp[i] = Math.max(dp[i - arr[j]] + 1, dp[i]);             }         }     }           return dp[N]; }   // Driver code const N = 17; const arr = [10, 11, 3]; console.log(cuttingRod(arr, N));

   3. Output

      3
      
      
      
      

   4. Time Complexity:
   5. O (N)
   6. Auxiliary Space:
   7. O (N)