algorithmrecursiondynamic-programming

Find the maximum number of pieces a rod can be cut


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.


Solution

  • 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));
    }