Grokking Dynamic Programming Interview in C++/

...

/

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 ≤100\leq 100

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

  • 0≤0 \leq n ≤105\leq 10^5

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
C++
usercode > main.cpp
int CountRibbonPieces(int n, std::vector<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. Given below is the possible ribbon sizes:

  • n: 33
  • sizes: [1,2,3][1, 2, 3]

Let’s look at all the possible combinations of ribbon sizes whose sum is equal to the n and we will select the maximum count of ribbon sizes out of them, that is 33:

  • 1,21, 2 => (1+2)(1+2) =3= 3
  • 1,1,11, 1, 1 => (1+1+1)(1+1+1) =3= 3

Below is the recursion tree for the above example, where at each level i, the left subtree indicates the inclusion of the sizes[i], and the right subtree indicates the exclusion of the sizes[i].

Access this course and 1400+ top-rated courses and projects.