Grokking Dynamic Programming Interview/

...

/

Maximum Ribbon Cut

Maximum Ribbon Cut

Let's solve the Maximum Ribbon Cut problem using Dynamic Programming.

We'll cover the following...

Statement

Given a ribbon of length n and a set of possible sizes, cut the ribbon in sizes such that n is achieved with the maximum number of pieces.

You have to return the maximum number of pieces that can make up n by using any combination of the available sizes. If the n can’t be made up, return -1, and if n is 0, return 0.

Let’s say, we have a ribbon of length 1313 and possible sizes as [5,3,8][5, 3, 8]. The ribbon length can be obtained by cutting it into one piece of length 55 and another of length 88 (as 5+8=135 + 8 = 13), or, into one piece of length 33 and two pieces of length 55 (as 3+5+5=133 + 5 + 5 = 13). As we wish to maximize the number of pieces, we choose the second option, cutting the ribbon into 33 pieces.

Constraints:

  • 1≤1 \leq sizes.length ≤12\leq 12

  • 1≤1 \leq sizes[i] ≤231−1\leq 2^{31} -1

  • 0≤0 \leq n ≤1500\leq 1500

Examples

No.

n

sizes

Count of Pieces

1

5

[1, 2, 3]

5

2

13

[5, 3, 8]

3

3

3

[5]

-1

Try it yourself

Implement your solution in the following playground:

Press + to interact
Java
usercode > RibbonCut.java
import java.util.*;
public class RibbonCut{
    public static int countRibbonPieces(int n, int[] sizes)
    {
        // write your code here
        return -1;
    }
}
Maximum Ribbon Cut

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Unbounded Knapsack dynamic programming pattern.

Naive approach

The naive approach is to generate all possible combinations of given ribbon sizes such that in each combination, the sum of ribbon sizes is equal to n. This can be achieved by recursively reducing the current ribbon length by available sizes until it reaches 0. From these combinations, choose the one with the maximum number of ribbon pieces and return that number. If the sum of any combinations is not equal to n then return -1.

For example, we have a ribbon of length 33 ...