Find the maximum number of pieces a rod can be cut

user_3357481 0
Viewed 2429

Here is the complete problem statement:

Given a rope of length n, you need to find the maximum number of pieces
you can make such that the length of every piece is in set {a, b, c} for
the given three values a, b, c

I know that the optimal solution can be achieved through Dynamic Programming, however, I have not learned that topic yet and I need to solve this problem recursively. With recursion, the main thing is to identify a subproblem and that's what I'm mainly having difficulty with doing. Can anyone give me an intuitive way to think of this problem? Sort of like a higher level description of the recursion if that makes sense. Is there an easier problem similar to this that I can try first that would help me solve this?



Thanks in advance.

dynamic-programming recursion algorithm
4 Answers

It's already quite simple, with recursion we can just check all posibilities, in one step we can either cut away a piece of length a, b, or c so from problem of size n we get sup-problem of smaller size n-x

Of course we need a base case, so when n=0 we have succeeded so we can return 0, in case of n < 0 we have failed so we can return some negative infinity constant

Sample pseudo-code:

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    return 1 + max(solve(n-a), solve(n-b), solve(n-c));
}

going to dynamic programming is as simple as setting up memo lookup table

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    if(n in memo)return memo[n]
    return memo[n] = 1 + max(solve(n-a), solve(n-b), solve(n-c));
}
user_40591450 
int maxcut(int n, int a,int b,int c)
{

    if(n==0) return 0;

    if(n<0) return 1;

    int result = max( maxcut(n-a,a,b,c), maxcut(n-b,a,b,c), maxcur(n-c,a,b,c));

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

    return(result+1)

 }
user_113425500

The way we should tackle the recursion problem is:

  1. Finding the recursion case (Finding the subproblems)
  2. Finding the base case (The last subproblem case we cannot break in subproblems)

Specific to this problem :

  1. Recursion case: Cutting rope we all the possible values till we cannot break it further smaller subproblem.
  2. Base case: a. It can be completely cut. (valid try) b.It can't be completely cut. (invalid try)

int maxcut(int n, int a,int b,int c) {

if(n==0) return 0; //base case a.

if(n<0) return -1; //base case b.

int result = max( maxcut(n-a,a,b,c), maxcut(n-b,a,b,c), maxcur(n-c,a,b,c)); //subproblems for all the cases

if(res == -1) return -1; // boundry coundtion

return(result+1); //to count the valid conditions and return to parent

}

user_138172760

here is the complete code for your problem

#include <iostream>
    using namespace std;
    int max(int a, int b, int c)
    {
        if (a > b)
        {
            if (a > c)
            {
    
                return a;
            }
        
        else
        {
            return c;
        }
        }
    
    else
    {
        if (b > c)
        {
    
            return b;
        }
    
        else
        {
            return c;
        }
    }
    
    }
    
    int maxpiece(int l, int a, int b, int c)
    {
        int r;
        if (l == 0) 
        {
            return 0;
        }
        if (l<0)
        {
            return -1;
        }
        
    
        r = max(maxpiece(l-a, a, b, c), maxpiece(l-b, a, b, c), maxpiece(l-c, a, b, c));
    
        if (r == -1)
            return -1;
    
        return r + 1;
    }
    
    int main()
    {
        int lenth;
        cout << "enter rope lenth ";
        cin >> lenth;
        int p1, p2, p3;
        cout << endl
             << "enter the only three parameters in which rope can be cut ";
        cin >> p1 >> p2 >> p3;
        cout << endl
             <<"ans = "<< maxpiece(lenth, p1, p2, p3);
    }
user_163839030
Related