Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview in Python

Maximum Ribbon Cut

Explore the maximum ribbon cut problem using dynamic programming under the unbounded knapsack pattern. Understand both naive recursive and optimized DP methods including top-down memoization and bottom-up tabulation. Gain skills to find the maximum number of ribbon pieces from given sizes and ribbon length, improving your problem-solving efficiency in technical interviews.

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 ...

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:

Python
usercode > main.py
import math



def count_ribbon_pieces(n, sizes):



  # write your code here



  return -1
Maximum Ribbon Cut
...