Rope Cutting Problem

PHOTO EMBED

Sun Feb 06 2022 21:32:20 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #recursion #rope cutting

import java.io.*;
import java.util.*;

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}
content_copyCOPY

Example 1: Input : n = 5, a = 2, b = 5, c = 1 Output : 5 (We make 5 pieces of length 1 each) Example 2: Input : n = 23, a = 12, b = 9, c = 11 Output : 2 (We make 2 pieces of length 11 and 12) Example 3: Input : n = 5, a = 4, b = 2, c = 6 Output : -1 (Not Possible)